转载

HDU(3374) (KMP + 最小表示法)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3374
最小表示法:http://tobyaa.blog.163.com/blog/static/30248591201261604349913/
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1000005; char str[maxn]; int next[maxn]; void get_next(char str[],int next[]){ int i = 0,j = -1; next[0] = -1; int len = (int)strlen(str); while(i < len){ if(j == -1 || str[i] == str[j]) next[++i] = ++j; else j = next[j]; } } int getmin(char str[]){ int len = (int)strlen(str); int i = 0,j = 1,k = 0; while(i < len && j < len && k < len){ int t = str[(i + k)%len] - str[(j + k)%len]; if(!t) k++; else{ if(t < 0) j += k+1; else i += k+1; if(i == j) j++; k = 0; } } return i>j?j:i; } int getmax(char str[]){ int len = (int)strlen(str); int i = 0,j = 1,k = 0; while(i < len && j < len && k < len){ int t = str[(i + k)%len] - str[(j + k)%len]; if(!t) k++; else{ if(t > 0) j += k+1; else i += k+1; if(i == j) j++; k = 0; } } return i>j?j:i; } int main(){ while(~scanf("%s",str)){ get_next(str, next); int len = (int)strlen(str); int time = 1; if(len%(len - next[len]) == 0) time = len/(len - next[len]); printf("%d %d %d %d\n",getmin(str)+1,time,getmax(str)+1,time); } return 0; }

 

转载于:https://www.cnblogs.com/Roly/archive/2013/05/14/3078281.html

正文到此结束
本文目录