admin 管理员组

文章数量: 887021

KMP = =

模板：

//s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组
int i,j;
for(i = 2,j = 0;i <= m;i ++)
{while(j && p[i] != p[j + 1])  j = ne[j];if(p[i] == p[j + 1])  j ++;ne[i] = j;
}//匹配
int i,j;
for(i = 1,j = 0; i <= n; i ++)
{while(j && s[i] != p[j + 1])  j = ne[j];if(s[i] == p[j + 1])  j ++;if(j == m){j = ne[j];//匹配成功后的逻辑 }
}

题目1：

Period

题目大意：

有多组测试用例，第一行为字符串长度，第二行为字符串，则对字符串的每一个前缀，若存在循环节且循环次数>1，输出长度和最大的循环次数；

每组测试用例后空一行；

SampleInput

3

aaa

12

aabaabaabaab

0

SampleOutput

Test case #1

2 2

3 3

Test case #2

2 2

6 2

9 3

12 4

写在前面：

Substr（i，j）表示的子串s[i...j].
这里的下标从1开始.
i的上一个匹配:一个位置j,满足Substr(1,j) == substr()
下面黑线表示字符串,其中红框中包含的字符相等(这是自然，同一个字符串嘛).
 

还要满足

（注意啦 两条黑线表示同一个字符串，只是位置不同）

下面图中红框中都表示相同

思路：

这题也可算是"拍大腿"系列了吧?其实你看看下面代码,真的很简单,关键就是如何推出这个结论.
(我不用next/fail,用了f做数组名,希望大家不要看不习惯,意思是一样的)

粉色部分也表示相同.这很明显，因为字符是一一对应的嘛(同一个字符串位置相同,长度相同的字符串当然一样).
由于红框内完全相同,还可以

 

继续对应!灰线表示在原字符串中是对应的.
还可以对应! 

可能就会出现这样的情况!(当然可能最前面不够长度)
因此，只要f[i] > 0,前面肯定有循环节!(只不过不知道是否完整,bb|abb|abb|abb这样也看作是)而且循环节长度为.因此只要判断循环节长度能否将长度整除即可.

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;char s[N];
int f[N];int main()
{int i;int n,k = 0;while(cin >> n && n != 0){int t = 0;cin >> s + 1;k ++;cout << "Test case #" << k << endl;f[1] = 0;for (i = 2; i <= n ; i ++ ){while (s[i] != s[t + 1] && t != 0)  t = f[t];if ( s[i] == s[t + 1] )  t++;f[i] = t;if(f[i] != 0 && i % ( i -  f[i] ) == 0)  cout << i << ' ' << i / ( i - f[i] ) << endl;}cout << endl;}return 0;
}

 

本文标签： KMP

版权声明：本文标题：KMP = = 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1693652862h234790.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。