首页 > 代码库 > 【NOI2016】优秀的拆分 题解（95分）
【NOI2016】优秀的拆分 题解（95分）
题目大意：
求一个字符串中形如AABB的子串个数。
思路：
用哈希做到O(1)判断字符串是否相同，O($n^2$)预处理，ans[i]为开头位置为i的形如AA的子串个数。再用O($n^2$)枚举出AABB中的AA，加上BB（已预处理）的个数即可。时间复杂度为O($n^2$),最后一个点过不掉~~。（此方法为在下所想的朴素算法，比不得大神们的方法，代码更是烂得要死）
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int S=999983,mod=100000009; 6 char s[40000]; 7 long long ans[40000],Hash[40000],mi[40000]; 8 9 int gethash(int l,int r)10 {11 return (Hash[r]-Hash[l-1]*mi[r-l+1]%mod+mod)%mod;12 }13 14 int main()15 {16 int n;17 scanf("%d",&n);18 while (n--)19 {20 int cnt,i,j;21 long long sum=0;22 scanf("%s",s+1); cnt=strlen(s+1);23 for (i=1;i<=cnt;i++) Hash[i]=(Hash[i-1]*S+s[i]-‘a‘+1)%mod;24 for (mi[0]=i=1;i<=cnt;i++) mi[i]=mi[i-1]*S%mod;25 for (i=1;i<=cnt;i++) ans[i]=0;26 for (i=1;i<=cnt;i++)27 for (j=i;j+j-i+1<=cnt;j++)28 if (gethash(i,j)==gethash(j+1,j+j-i+1)) ans[i]++;29 for (i=2;i<cnt-1;i++)30 for (j=i;j>i+1>>1;j--)31 if (gethash(j,i)==gethash(j-i+j-1,j-1)) sum+=ans[i+1];32 printf("%d\n",sum);33 }34 return 0;35 }
【NOI2016】优秀的拆分 题解（95分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。