POJ 2406 Power Strings
题目意思为求一个最小的子串,使原串由 n 个子串连接而成。 假设子串长度为 k, 则对于该字符串有
S[1, len(S)- k]== S[k+ 1, len(S)], 且 k 最小, 也说是 len(S)- k最大,这恰好是 KMP 算法中
的 next[] 数组。求出 next[ len(S) ], 则 len(S)- next[ len(S) ] 为子串的长度。
代码:
#include <stdio.h>
#include <string.h>
char str[1000001];
int next[1000001];
int main(){
while( gets(str)!= NULL ){
if( strcmp( str, "." )== 0 ) return 0;
int i= 0, j= -1; next[0]= -1;
while( str[i] ){
if( j== -1 || str[i]== str[j] ){
i++; j++; next[i]= j;
}
else j= next[j];
}
int len= i; i-= j;
if( len% i== 0 ) printf("%d\n", len/ i );
else printf("1\n");
}
return 0;
}
|
HDU 3366 代码:
#include <stdio.h>
#include <stdlib.h>
#define N 200010
char str[N];
int n, next[N], dp[N];
int main(){
int test;
scanf("%d",&test );
while( test-- ){
scanf("%d",&n );
scanf("%s", str );
int i= 0, j= -1; next[0]= -1;
while( str[i] ){
if( j== -1 || str[i]== str[j] ){
i++; j++; next[i]= j; }
else j= next[j];
}
next[n]= j;
for( int i= 0; i<= n; ++i ) dp[i]= 1;
for( int i= n; i> 0; i-- )
if( next[i]> 0 ) dp[ next[i]- 1]+= dp[i];
int ans= 0;
for( int i= 0; i< n; ++i )
ans= ( ans+ dp[i] ) % 10007;
printf("%d\n", ans );
}
return 0;
}
|
阅读(403) | 评论(0) | 转发(0) |