题目大意:给出一个字符串,将其分解为若干子串的和,求可分解的最多子串的个数。
做题之前就知道这是一道KMP的题目,但一直没想到怎么写 后面看了下别人的思路(最近写题总是会忍不住看别人的思路 惭愧。。) 得出结论: 一个串的周期子串长度=主串长-next[主串长度]. 然后再用主串长除以周期子串长度就得到了子串周期长度。
下面贴代码
#include "iostream" using namespace std; #define len 1000020 char c[len]; int next[len]; int clen; void getnext() { int i; int j; i=0; j=-1; next[0]=-1; while (i<clen) { if (j==-1||c[i]==c[j]) { i++; j++; next[i]=j; } else { j=next[j]; } } } int main() { while (true) { scanf("%s",c); if (c[0]=='.') { break; } clen=strlen(c); getnext(); int t=clen-next[clen]; if (c[clen-1]!=c[t-1]) { printf("1\n");//注意考虑如aabaabaa 这种结果为1的情况 } else { printf("%d\n",clen/(clen-next[clen])); } } return 0; }
相关推荐
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大POJ1159-Palindrome