扩展KMP题目

时间:2022-02-06 12:34:24

hdu4333

/*
题意:字符串s[0..n-1],每次把最后一个字符放到前面,求形成的字符串比最初串分别小,相同,大于的个数
因为是为了练习扩展KMP所以肯定是扩展KMP,
为了循环方便,在后面复制字符串,求出next[]数组后,
如果next[i]>n那么肯定相等,如果小于就判断s[ next[i] ]和 s[ i+next[i] ]的大小判断 trick:题目求得是形成的不同的字符串的个数,可以知道相等的字符串肯定只有一个,
而从0..n-1,第二个next[i]大于n那么这个i就是该字符串的循环节;
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=+;
char s[N*];
int next[N*],n; void getNext(char *s,int next[]){
int nn=strlen(s);
next[]=nn;
int p=;
while (s[p+] && s[p]==s[p+]) p++;
next[]=p;
int k=;
for (int i=;i<nn;i++){
int p=k+next[k]-, L=next[i-k];
if (i+L<=p) next[i]=L;
else{
int j=p-i+;
if (j<) j=;
while (i+j<nn && s[i+j]==s[j]) j++;
next[i]=j; k=i;
}
} } void work(){
int ret1,ret2,ret3;
ret1=ret2=ret3=;
getNext(s,next);
for (int i=;i<n;i++){
if (i!= && next[i]>=n) break;
if (next[i]<n) {
if (s[ i+next[i] ]<s[ next[i] ]) ret1++;
else ret3++;
}else ret2++;
}
printf("%d %d %d\n",ret1,ret2,ret3);
}
int main(){
int T,cas=;scanf("%d",&T);
while (T--){
scanf("%s",s);
printf("Case %d: ",++cas);
n=strlen(s);
for (int i=;i<n;i++){
s[n+i]=s[i];
}s[n+n]='\0';
// cout<<s<<endl;
work();
}
return ;
}

hdu3613

 /*
题意:将一个串分成俩个串,如果是回文串值就是所有字符的值,如果不是值就为0
问你最大的值是多少; 分析:因为是扩展KMP的题,很容易想到用扩展KMP判读是否是回文串,而且题目的
特点是至少有一端是端点,这很容易想到前缀和后缀,然后思路就出来了;
首先将串s逆转变成s1,求出s的所有后缀与s1的最长公共子串的长度,
这样分割成两段的后面一段,判断该段是否是回文只要判断最长长度是否等于后面一段的 长度就可以了了
前面一段类似,只是要求出s1的所有后缀与s的最长公共子串的长度,判断方法类似 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=+;
char s[N],s1[N];
int v[];
int ext1[N],ext2[N],next[N];
void getNext(char *s,int next[]){
int nn=strlen(s);
next[]=nn;
int p=;
while (s[p+] && s[p]==s[p+]) p++;
next[]=p;
int k=, L;
for (int i=;i<nn;i++){
p=k+next[k]-; L=next[i-k];
if (i+L<=p) next[i]=L;
else {
int j=p-i+;
if (j<) j=;
while (i+j<nn && s[i+j]==s[j]) j++;
next[i]=j; k=i;
}
} }
void getExtend(char *s,char *T,int *ext){
getNext(s,next);
int p=, nn=strlen(s);
while (s[p] && s[p]==T[p]) p++;
ext[]=p;
int k=, L;
for (int i=;i<nn;i++){
p=k+ext[k]-; L=next[i-k];
if (i+L<=p) ext[i]=L;
else {
int j=p-i+;
if(j<) j=;
while (i+j<nn && s[i+j]==T[j]) j++;
ext[i]=j; k=i;
}
}
}
int val[N];
void work(){
memset(val,,sizeof(val));
int len=strlen(s);
for (int i=;i<len;i++) val[i+]=val[i]+v[s[i]-'a']; for (int i=len-;i>=;i--) s1[len-i-]=s[i];
s1[len]='\0';
// cout<<s<<endl<<s1<<endl;
getExtend(s1,s,ext1);
getExtend(s,s1,ext2); int ret=;
for (int i=;i<len;i++){
int l1=i,l2=len-l1;
int tmp=;
if (ext1[len-i]==l1) tmp+=val[i];
if (ext2[i]==l2) tmp+=val[len]-val[i];
if (tmp>ret) ret=tmp;
}
printf("%d\n",ret);
}
int main(){
int T;scanf("%d",&T);
while (T--){
for (int i=;i<;i++) scanf("%d",v+i);
scanf("%s",s);
work();
}
return ;
}
/*
4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aaadbbbd
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
ab
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aba
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aaaaaaaaaaaaaaa */

poj1699

 /*
题意:给你n个串,求最短的串使得n个串都包含在里面(n<=10)
从n的数据范围就可以看出状态压缩dp
dp[i][j]表示已经包含了"i"个串,且最后一个串是j的最小长度
预处理出s[i]的后缀与s[j]的前缀的最长公共子串 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=+;
char s[N][N];
int n,next[N],mz[N][N],ext[N];
void getNext(char *s,int *next){
int nn=strlen(s);
next[]=nn;
int p=;
while (s[p+] && s[p]==s[p+]) p++;
next[]=p;
int k=, L;
for (int i=;i<nn;i++){
p=k+next[k]-; L=next[i-k];
if (i+L<=p) next[i]=L;
else{
int j=p-i+;
if (j<) j=;
while (i+j<nn && s[i+j]==s[j]) j++;
next[i]=j; k=i;
}
}
}
void getExtend(char *s,char *T,int ext[]){
getNext(s,next);
int nn=strlen(s);
int p=;
while (s[p] && T[p] && s[p]==T[p]) p++;
ext[]=p;
int k=,L;
for (int i=;i<nn;i++){
p=k+ext[k]-; L=next[i-k];
if (i+L<=p) ext[i]=L;
else {
int j=p-i+;
if (j<) j=;
while (i+j<nn && s[i+j]==T[j]) j++;
ext[i]=j; k=i;
}
}
}
void init(){
memset(mz,,sizeof(mz));
for (int i=;i<n;i++){
for (int j=;j<n;j++){
if (i==j) continue;
getExtend(s[i],s[j],ext);
int nn=strlen(s[i]);
for (int k=;k<nn;k++){
if (ext[k]==nn-k) {
mz[i][j]=nn-k; break;
}
}
}
}
/*for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
cout<<mz[i][j]<<" ";
}cout<<endl;
}*/
}
const int NN=<<;
int dp[NN][];
void Min(int &x,int y){
if (x==-) x=y;
else x=min(x,y);
}
void work(){
memset(dp,-,sizeof(dp));
for (int i=;i<n;i++){
dp[<<i][i]=strlen(s[i]);
}
for (int i=;i<(<<n);i++){
for (int j=;j<n;j++){
if (dp[i][j]==-) continue;
for (int k=;k<n;k++){
if ( i&(<<k) ) continue;
Min(dp[i^(<<k)][k],dp[i][j]+strlen(s[k])-mz[j][k]);
}
}
}
int ret=-;
for (int i=;i<n;i++){
Min(ret,dp[(<<n)-][i]);
}
cout<<ret<<endl; }
int main(){
int T;scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=;i<n;i++) scanf("%s",s[i]);
init();
work();
}
return ;
}