快速读入
可以根据题目描述自行修改。
void Init()
{
char ch;
ch = getchar();
while (ch < 'A' || ch > 'Z')
ch = getchar();
while (ch >= 'A' && ch <= 'Z')
{
A[++lena] = ch;
ch = getchar();
}
while (ch < 'A' || ch > 'Z')
ch = getchar();
while (ch >= 'A' && ch <= 'Z')
{
B[++lenb] = ch;
ch = getchar();
}
}
KMP
(A) 为大串,(B) 为小串。
求 (next) 数组
void make_nxt()
{
j = 0;
for (int i = 2; i <= lenb; ++i)
{
while (B[i] != B[j + 1] and j)
j = nxt[j];
if (B[i] == B[j + 1])
++j;
nxt[i] = j;
}
}
匹配
void check()
{
j = 0;
for (int i = 1; i <= lena; i++)
{
while (A[i] != B[j + 1] and j)
j = nxt[j];
if (A[i] == B[j + 1])
++j;
if (j == lenb)
{
printf("%lld
", i - lenb + 1);
j = nxt[j];
}
}
}
题目详解
P4391 [BOI2009]Radio Transmission
观察题目性质,可得:(ans=n-nxt[n])。
直接切
int main()
{
n = read();
for (int i = 1; i <= n; ++i)
B[i] = getchar();
make_nxt();
printf("%lld
", n - nxt[n]);
}
P3435 [POI2006]OKR-Periods of Words
题意简述:
对于给定串的每个前缀 (i),求最长的,使这个字符串重复两边能覆盖原前缀 (i) 的前缀(就是前缀 (i) 的一个前缀),求所有的这些“前缀的前缀”的长度和。
分析:
利用 (next) 的性质:前缀 (i) 的长度为 (next[i]) 的前缀和后缀是相等的
如果有 (i) 一个公共前后缀长度为 (j),那么这个前缀 (i) 就有一个周期为 (i-j)。
做法:
先求出 (next) 数组
对于每个前缀 (i),令 (j=i),然后在 (j>0) 的情况下令 (j=next[j]),最小的 (j) 就是答案,此时 (ans+=i−j)。
一个优化:求出 (j) 以后,令 (j=fail[i]),这样能加快递归速度(相当于记忆化了)
const ll N = 1e7 + 2;
ll n, nxt[N];
char B[N];
void make_nxt()
{
ll k = 1;
for (ll i = 2; i <= n; ++i)
{
while ((B[k] != B[i] && k > 1) || k > i)
k = nxt[k - 1] + 1;
if (B[k] == B[i])
nxt[i] = k++;
}
}
ll ans = 0;
int main()
{
// freopen("P3435_1.in", "r", stdin);
n = read();
for (ll i = 1; i <= n; ++i)
cin >> B[i];
make_nxt();
for (ll i = 1; i <= n; ++i)
{
ll j = i;
while (nxt[j])
j = nxt[j];
if (nxt[i])
nxt[i] = j;
ans += 1LL * (i - j);
}
printf("%lld
", ans);
}
P4824 [USACO15FEB]Censoring S
( ext{KMP}) 的删除操作。
在匹配过程中,如果匹配成功了,就将子串 (B) 删除,可以证明,对之前不会产生影响。
删了再加入,类似栈的操作,因此用栈维护上述操作过程中的字串即可。
时间复杂度:(B) 自身匹配一次 (+A) 与 (B) 匹配一次 (+A) 中最多每个字符进出栈一次,为 (O(∣A∣))
const ll N = 10000003;
ll k, lena, lenb, nxt[N];
char A[N], B[N];
int stk[N], top, pos[N];
void Init()
{
char ch;
ch = getchar();
while (ch < 'a' || ch > 'z')
ch = getchar();
while (ch >= 'a' && ch <= 'z')
{
A[++lena] = ch;
ch = getchar();
}
while (ch < 'a' || ch > 'z')
ch = getchar();
while (ch >= 'a' && ch <= 'z')
{
B[++lenb] = ch;
ch = getchar();
}
}
void make_nxt()
{
k = 1;
for (int i = 2; i <= lenb; ++i)
{
while ((B[k] != B[i] && k > 1) || k > i)
k = nxt[k - 1] + 1;
if (B[k] == B[i])
nxt[i] = k++;
}
}
void check()
{
k = 0;
for (int i = 1; i <= lena; ++i)
{
while (B[k + 1] != A[i] && k > 0)
k = nxt[k];
if (B[k + 1] == A[i])
k++;
pos[i] = k;
stk[++top] = i;
if (k == lenb)
{
top -= lenb;
k = pos[stk[top]];
}
}
}
int main()
{
Init();
make_nxt();
check();
for (int i = 1; i <= top; ++i)
printf("%c", A[stk[i]]);
Edison Ba;
}