2295: KMP模式匹配 一（串）
2295: KMP模式匹配 一（串）
时间限制: 1 Sec 内存限制: 128 MB提交: 210 解决: 97
[提交][状态][讨论版][命题人:外部导入]
题目描述
求子串的next值，用next数组存放，全部输出
输入
输入一个字符串
输出
输出所有next值
样例输入
abaabcac
样例输出
0 1 1 2 2 3 1 2
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10010;
int len;
void getnext(char s[maxn], int next[maxn])
{
len = strlen(s);
int i = 0, j = -1;
next[0] = -1;
while(i < len)
{
if(j == -1 || s[i] == s[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int main()
{
char a[maxn];
int next[maxn];
int i;
cin >> a;
len = strlen(a);
getnext(a, next);
for(i = 0; i < len - 1; ++i)
{
printf("%d ", next[i] + 1);
}
printf("%d", next[i] + 1);
return 0;
}