首页 > 代码库 > loj6158 A+B Problem (扩展KMP)

loj6158 A+B Problem (扩展KMP)

2024-10-15 03:10:03   214人阅读

题目：

https://loj.ac/problem/6158

分析：

先把S串逆置，就是从低位向高位看

我们再弄个T串，S串前面有x个连续的0，那么T串前面也有x个连续的0

第x+1位，满足S[x+1]+T[x+1]=10

后面的位置，均满足S[j]+T[j]=9

然后我们发现S的每一个后缀S[i]与T串进行匹配，求个最长的前缀就是当前在这个位置劈开的结果

这个是个典型的扩展KMP的应用，即对于S、T串，求S的每个后缀S[i]与T的最长公共前缀

本题有几点细节：

1、因为最高位之前的那些位置都是0，所以在S串的后面，需要加上一些0

2、要注意当某个S[i]和T的最长公共前缀超过了i的位置，那么超过i的那些位置并不是我们想要的，实际上，那些应该是99999999……或者000000........

所以可以预处理出S的每一位后面有多少连续的0和多少个连续的9

技术分享
 1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=1e6; 6 char S[2*maxn+50],T[maxn+50];//S是母串，T是子串 7 int len1,len2; 8 int next[maxn+50],extend[2*maxn+50];//extend[i]表示S[i..len1-1]和T的最长公共前缀的长度，next[i]表示T[i..len2-1]和T的最长公共前缀的长度 9 int num9[maxn+50];10 int num0[maxn+50];11 void getnext()12 {13     next[0]=len2;14     int j=0;15     while(j+1<len2&&T[j]==T[j+1]) ++j;16     next[1]=j;17     int k=1;18     for(int i=2;i<len2;++i)19     {20         int p=k+next[k]-1,l=next[i-k];21         if(i+l<p+1) next[i]=l;22         else23         {24             j=max(p-i+1,0);25             while(i+j<len2&&T[i+j]==T[j]) ++j;26             next[i]=j;27             k=i;28         }29     }30 }31 void ekmp()32 {33     int j=0;34     while(j<len1&&j<len2&&S[j]==T[j]) ++j;35     extend[0]=j;36     int k=0;37     for(int i=1;i<len1;++i)38     {39         int p=k+extend[k]-1,l=next[i-k];//p表示到达的最远位置，k是对应最远位置的i40         if(i+l<p+1) extend[i]=l;41         else42         {43             j=max(p-i+1,0);44             while(i+j<len1&&j<len2&&S[i+j]==T[j]) ++j;45             extend[i]=j;46             k=i;47         }48     }49 }50 int main()51 {52 53     while (scanf("%s",S)!=EOF)54     {55         len1=strlen(S);56         for(int i=0;i<len1/2;++i) swap(S[i],S[len1-i-1]);57         int i=0;58         for(i=0;S[i]==‘0‘;++i) T[i]=‘0‘;59         T[i]=‘9‘+1-S[i]+‘0‘;60         ++i;61         for(i;i<len1;++i)62             T[i]=‘9‘-S[i]+‘0‘;63         T[len2=len1]=‘\0‘;64         for(int i=len1;i<len1+len2;++i) S[i]=‘0‘;65         S[len1+len2]=‘\0‘;66         len1=strlen(S);67         memset(num9,0,sizeof(num9));68         memset(num0,0,sizeof(num0));69         for(int i=len2-1;i>=0;--i)70         {71             if(S[i+1]!=‘9‘) num9[i]=0;else num9[i]=num9[i+1]+1;72             if(S[i+1]!=‘0‘||i==len2-1) num0[i]=0;else num0[i]=num0[i+1]+1;73         }74         memset(next,0,sizeof(next));75         memset(extend,0,sizeof(extend));76         getnext();77         ekmp();78         int ans=0;79         for(int i=1;i<len2;++i)80         {81             if(extend[i]>=i)82             {83                 if(S[i]==‘0‘&&num0[i]>=i-1) ans=max(ans,num0[i+i-1]+i);84                 else ans=max(ans,num9[i+i-1]+i);85             }86             else87              ans=max(ans,extend[i]);88         }89         printf("%d\n",ans);90     }91     return 0;92 }
View Code

 

loj6158 A+B Problem (扩展KMP)


联系
我们