CF #93 div1 B. Password KMP/Z

题目链接:http://codeforces.com/problemset/problem/126/B

大意:给一个字符串,问最长的既是前缀又是后缀又是中缀(这里指在内部出现)的子串。

我自己的做法是用KMP的next数组,对所有既是前缀又是中缀的位置计数,再从next[n]开始走next,也即枚举所有既是前缀又是后缀的子串,看cnt[i]是否大于0,如果大于0则说明作为中缀出现过(也即有大于i的某个位置的next为i)

 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int next[N];
int cnt[N];
void getNext(char *word,int n=){
n=(n==)?strlen(word):n;
memset(next,,sizeof(next));
int i,j;
for (i=;i<n;i++){
j=i;
while (j){
j=next[j];
if (word[i]==word[j]){
next[i+]=j+;
break;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
getNext(s,n);
for (int i=;i<n;i++)
cnt[next[i]]++;
if (next[n]==)
puts("Just a legend");
else {
for (int i=next[n];i;i=next[i]) {
if (cnt[i]) {
for (int j=;j<i;j++)
printf("%c",s[j]);
puts("");
return ;
}
}
puts("Just a legend");
}
return ;
}

还有一种枚举方法是扫描所有可能的中缀末位,取next[i]的最大值,也即求出最大的既是前缀又是中缀的子串,再从next[n]开始走next,第一次走到0<next[i]<=len时,也即找到了子串。

 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int next[N];
void getNext(char *word,int n=){
n=(n==)?strlen(word):n;
memset(next,,sizeof(next));
int i,j;
for (i=;i<n;i++){
j=i;
while (j){
j=next[j];
if (word[i]==word[j]){
next[i+]=j+;
break;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
getNext(s,n);
int len=;
for (int i=;i<n;i++)
len=max(len,next[i]);
for (int i=next[n];i>;i=next[i]) {
if (i>len) continue;
for (int j=;j<i;j++)
printf("%c",s[j]);
puts("");
return ;
}
puts("Just a legend");
return ;
}

第三种方法是用z算法,也就是算出每个位置与本串的最长公共前缀。再枚举所有后缀,check当前后缀是否也是前缀,如果是的话,则看之前是否有z[i]也就是与本串的LCP大于当前后缀长度,如果有,则当前后缀也一定可以作为中缀出现,当前后缀是最长的符合题意的子串。

 #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <map>
#include <set> using namespace std; const int N=1e6+;
char s[N];
int z[N];
void Z_match(char *s,int n=) {
n=(n==)?strlen(s):n;
z[]=n;
int l=,r=;
for (int i=;i<n;i++) {
if (i>r) {
l=i,r=i;
while (r<n&&s[r-i]==s[r]) r++;
z[i]=r-l;
r--;
}
else {
int k=i-l;
if (z[k]<r-i+)
z[i]=z[k];
else {
l=i;
while (r<n&&s[r-i]==s[r]) r++;
z[i]=r-l;
r--;
}
}
}
}
int main () {
scanf("%s",s);
int n=strlen(s);
Z_match(s,n);
int ret=,maxZ=;
for (int i=;i<n;i++) {
if (z[i]==n-i) {
if (maxZ>=n-i) {
ret=n-i;
break;
}
}
maxZ=max(maxZ,z[i]);
}
if (ret==)
puts("Just a legend");
else {
for (int i=;i<ret;i++)
printf("%c",s[i]);
puts("");
}
return ;
}
上一篇:清理SharePoint 2010的SQL Server 2008 R2日志数据库的方法!


下一篇:myhandle