|
POJ? 2406 題意：求最長循環(huán)節(jié) 題解：Next數組的使用，判斷 len/ (len-Next[len])， 注意Next[] != 0要特別判斷一下；? 
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6 5;
int Next[maxn], m, n;
char x[maxn], y[maxn];
void KMP_Pre()
{
int i=0, j=-1;
Next[0]=-1;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
while(cin>>x, x[0]!='.')
{
m=strlen(x);
int ans=1;
KMP_Pre();
if(m%(m-Next[m])==0)
ans=m/(m-Next[m]);
cout<<ans<<endl;
}
return 0;
}
View Code
? HDU 3746 題意: 補齊循環(huán)節(jié)，求最少添加多少個字符，能獲得循環(huán)節(jié) 題解：畫個圖看看就行了，可發(fā)現 (len x)/ (len x-Next[len] x) 注意Next[] != 0要特別判斷一下；
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6 5;
int Next[maxn], m, n;
char x[maxn], y[maxn];
void KMP_Pre()
{
int i=0, j=-1;
Next[0]=-1;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
int T; cin>>T;
while(T--)
{
cin>>x;
m=strlen(x);
KMP_Pre();
int ans;
if(Next[m]!=0 && m%(m-Next[m])!=0)
ans=(m-Next[m])-m%(m-Next[m]);
else if(Next[m]==0)
ans=m;
else
ans=0;
cout<<ans<<endl;
}
return 0;
}
View Code
? HDU 1358 題意：求前綴的循環(huán)節(jié) 題解：和前面一樣直接判斷取余后是否有余數即可
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6 5;
int Next[maxn], m, n;
char x[maxn], y[maxn];
void KMP_Pre()
{
int i=0, j=-1;
Next[0]=-1;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
int kase=0;
while(cin>>m, m)
{
cin>>x;
KMP_Pre();
printf("Test case #%d\n", kase);
for(int i=2; i<=m; i )
{
if(Next[i]>0 && i%(i-Next[i])==0)
printf("%d %d\n", i, i/(i-Next[i]));
}
printf("\n");
}
return 0;
}
View Code
? HDU 2087? 題意：求子串在母串出現的次數（不重疊） 題解：每次匹配完成后講j指向0即可
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5 5;
int Next[maxn], m, n;
char x[maxn], y[maxn];
void KMP_Pre()
{
int i=0, j=-1;
Next[0]=-1;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
int KMP_Count()
{
int i=0, j=0;
int ans=0;
KMP_Pre();
while(i<n)
{
while(j!=-1 && y[i]!=x[j])
j=Next[j];
i ; j ;
if(j>=m){
ans ; j=0;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
while(cin>>y>>x, y[0]!='#')
{
m=strlen(x);
n=strlen(y);
cout<<KMP_Count()<<endl;
}
return 0;
}
View Code
? POJ 2752? 題意：求既是前綴又是后綴的子串長度 ；? 題解：這題比之前的要難一點，這個是非常清晰Next數組和KMP算法的過程；? Next數組記錄的就是前綴串，若Next[len]==s[len-1] 即前后綴相等，然后不斷迭代Next[len]并判斷即可，然后判斷s[next[next[n-1]]] == s[n-1]是否成立，這樣一直回滾，直到next[next[.....next[n-1]]] == -1為止。
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6 5;
int Next[maxn], m, n;
char x[maxn], y[maxn];
void KMP_Pre()
{
int i=0, j=-1;
Next[0]=-1;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
int ans[maxn];
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt", "r", stdin);
while(cin>>x)
{
m=strlen(x);
KMP_Pre();
int pre=m-1, cnt=1;
while(pre!=-1)
{
if(x[pre]==x[m-1])
ans[cnt ]=pre 1;
pre=Next[pre];
}
while(--cnt)
cout<<ans[cnt]<<" ";
cout<<endl;
}
return 0;
}
View Code
? POJ 3080 題意：找多個串之間的公共子串，輸出最大的（數據量很?。?/p> 題解：暴力截取 KMP匹配判斷，維護一個最大的即可；? 
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string str[100], s[100];
int Next[100];
void KMP_Pre(string x, int m)
{
int i=0, j=-1;
Next[0]=-1;
while(i<m) // 這個之前錯寫成j<m
{
while(j!=-1 && x[i]!=x[j])
j=Next[j];
Next[ i]= j;
}
}
bool KMP(string x, int m, string y, int n)
{
//KMP_Pre(x, m);
int i=0, j=0;
while(i<n)
{
while(j!=-1 && y[i]!=x[j])
j=Next[j];
i; j;
if(j>=m)
return true;
}
return false;
}
int main()
{
//freopen("in.txt", "r", stdin);
int T; cin>>T;
while(T--)
{
int num; cin>>num;
for(int i=0; i<num; i )
cin>>str[i];
string ans="";
for(int len=1; len<=str[0].size(); len ) //這個等于之前丟了...
for(int i=0; i len<=str[0].size(); i )
{
bool flag=1;
string p=str[0].substr(i, len);
KMP_Pre(p, p.size());
for(int k=1; k<num; k )
if( !KMP(p, p.size(), str[k], str[k].size()) ){
flag=0; break;
}
if(flag)
{
if(ans.size()<p.size())
ans=p;
else if(ans.size()==p.size())
ans=min(ans,p);
}
}
if(ans.size()<3)
cout<<"no significant commonalities"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
View Code
? 來源：http://www./content-1-183551.html |
|
|
