搞笑的题
这题其实类似于上面的一个也和前缀有关的题
就是不断地套next
但是刚开始我理解错题义了
直接开始二分
更离谱的是我二分还写错了,没有写r=mid-1这一句
然后我ac了真的是离谱
#include<cstdio> #include<cstring> using namespace std; const int max_n = 1e6+100; int n; int net[max_n]; void getnext(char p[]){ net[0]=-1; for (int i=0,j=-1;i<n;){ if (j==-1||p[i]==p[j])net[++i]=++j; else j = net[j]; } } bool kmp(int len,char p[]){ int l = len;int r = n-len-1; for (int i=l,j=0;i<=r;){ if (j==-1||p[i]==p[j]){++i;++j;} else j=net[j]; if (j==len)return true; }return false; } char s[max_n]; int main(){ int T;scanf("%d",&T); while (T--){ scanf("%s",s); n = strlen(s); getnext(s); int len = net[n]; while (len){ if (len*3<=n&&kmp(len,s))break; len=net[len]; }printf("%d\n",len); } }
但是这个复杂度会是多少呢?
我有点迷茫。