记录编号 |
165101 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HEOI 2015]最短不公共子串 |
最终得分 |
100 |
用户昵称 |
Chenyao2333 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.718 s |
提交时间 |
2015-06-10 10:19:08 |
内存使用 |
62.51 MiB |
显示代码纯文本
// Orz ztx
// Orz ztx
// Orz ztx
// The important thing need say 3 times
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int kSZC = 26;
const int kN = 2000+10;
const int kS = 4000+10;
const int INF = 1e9;
char str_a[kN], str_b[kN];
int a_len, b_len;
struct Node {
int len, link;
int nxt[kSZC];
}A[kS], B[kS];
int node_cnt;
int Insert(int last, int c, Node t[]) {
int cur = ++node_cnt;
t[cur].len = t[last].len+1;
for (int p = last; p != -1; p = t[p].link) {
if (!t[p].nxt[c]) {
t[p].nxt[c] = cur;
} else {
int q = t[p].nxt[c];
if (t[p].len+1 == t[q].len) {
t[cur].link = q;
} else {
int clone = ++node_cnt;
t[clone] = t[q];
t[clone].len = t[p].len+1;
for (int tp = p; tp != -1 && t[tp].nxt[c] == q; tp = t[tp].link) {
t[tp].nxt[c] = clone;
}
t[q].link = t[cur].link = clone;
}
break;
}
}
return cur;
}
void BuildSam(char str[], int n, Node t[]) {
node_cnt = 0;
memset(t, 0, sizeof(Node)*kS);
t[0].link = -1;
int last = 0;
for (int i = 1; i <= n; i++) {
last = Insert(last, str[i]-'a', t);
}
}
void BuildTrans(char str[], int n, Node t[]) {
memset(t, 0, sizeof(Node)*kS);
for (int i = n-1; i >= 1; i--) {
int c = str[i+1]-'a';
for (int j = 0; j < kSZC; j++) {
if (j == c) {
t[i].nxt[j] = i+1;
} else {
t[i].nxt[j] = t[i+1].nxt[j];
}
}
}
for (int i = 1; i <= n; i++) {
int c = str[i] - 'a';
if (!t[0].nxt[c]) {
t[0].nxt[c] = i;
}
}
}
int d[kS][kS];
int Solve() {
for (int i = 0; i < kS; i++) for (int j = 0; j < kS; j++) d[i][j] = INF;
queue<pair<int, int> > q;
d[0][0] = 0;
q.push(make_pair(0, 0));
while (q.size()) {
int l = q.front().first, r = q.front().second;
q.pop();
for (int c = 0; c < kSZC; c++) {
int tl = A[l].nxt[c];
int tr = B[r].nxt[c];
if (tl && !tr) return d[l][r]+1;
if (tl && d[tl][tr] > d[l][r]+1) {
d[tl][tr] = d[l][r]+1;
q.push(make_pair(tl, tr));
}
}
}
return -1;
}
int main() {
//freopen("in.txt", "r", stdin);
freopen("sus.in", "r", stdin);
freopen("sus.out", "w", stdout);
scanf("%s %s", str_a+1, str_b+1);
a_len = strlen(str_a+1);
b_len = strlen(str_b+1);
int ans1, ans2, ans3, ans4;
BuildSam(str_a, a_len, A);
BuildSam(str_b, b_len, B);
ans1 = Solve();
BuildTrans(str_b, b_len, B);
ans2 = Solve();
BuildTrans(str_a, a_len, A);
ans4 = Solve();
BuildSam(str_b, b_len, B);
ans3 = Solve();
printf("%d\n%d\n%d\n%d\n", ans1, ans2, ans3, ans4);
return 0;
}