?? 1905(kmp).cpp
字號(hào):
//zoj 1905 KMP
/*
設(shè)串長為len,先求出next[len]
然后判斷l(xiāng)en是否能被len - next[len] 整除,能則輸出len / (len - next[len])
不能輸出1
*/
#include <iostream.h>
#include <string>
using namespace std;
int next[1000002];
string str;
void get_next(string T,int next[])
{
int i=1,j=0;
next[1]=0;
while(i<=T.length())
{
if(j==0 || T[i]==T[j])
{ ++i;++j;
if(T[i]!=T[j]) next[i]=j;
else next[i]=next[j];//消去多余的可能的比較,next再向前跳
}
else j=next[j];
}
}
int main()
{
int len;
while(cin>>str && str!=".")
{
len=str.length();
get_next(str,next);
if(len%(len-next[len])==0)
cout<<len/(len-next[len])<<endl;
else
cout<<"1"<<endl;
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -