poj 2406 Power Strings
poj POWER strings
2023-09-11 14:20:42 时间
题意:求给定字符串最大循环次数
思路:依据KMP算法的next数组知,一个长度为n的字符串,
if(n%(n-next[n])==0)
最小循环长度为 L=n-next[n];
最大循环次数为 S=n/L=n/(n-next[n]);
#include<stdio.h> #include<string.h> int next[1001010]={-1},n; char s[1001010]; int getnext() { int i=0,j=-1; while(i<n){ if(j==-1||s[i]==s[j]){ i++; j++; next[i]=j; } else j=next[j]; } if(n%(n-next[n])==0) return n/(n-next[n]); return 1; } int main() { while(scanf("%s",s)!=EOF){ if(strcmp(s,".")==0) break; n=strlen(s); n=getnext(); printf("%d\n",n); } return 0; }
相关文章
- 最后一个非零数字(POJ 1604、POJ 1150、POJ 3406)
- POJ 1716 区间最小点个数
- Power Network (poj 1459 网络流)
- POJ 2763 Housewife Wind
- POJ 3869 Headshot
- POJ 3667 Hotel
- POJ 3694 Network
- POJ 1321 棋盘问题
- POJ 1469 COURSES
- 【POJ 1112】Team Them Up!(二分图染色+DP)
- POJ 3122 Pie
- POJ 3130 How I Mathematician Wonder What You Are! /POJ 3335 Rotating Scoreboard 初涉半平面交
- poj 3592 Instantaneous Transference 【SCC +缩点 + SPFA】
- poj - 2823 - Sliding Window(单调队列)
- nyoj 163 Phone List(动态字典树<trie>) poj Phone List (静态字典树<trie>)