首页 > 代码库 > hdu3374 kmp+最小表示法
hdu3374 kmp+最小表示法
Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:
String Rank
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
String Rank
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Input Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.OutputOutput four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.Sample Input
abcder aaaaaa ababab
Sample Output
1 1 6 1 1 6 1 6 1 3 2 3
题意:找出一个字符串的循环列中最小和最大的那个字符串,并求出格数
题解:个数就是最小循环数,用kmp的next数组即可,然后用字符串的最小表示法求,最大的同理wa点:刚开始想直接暴力结果mle,莫名其妙,我以为应该是tle,结果改用kmp了之后,直接暴力求最小还是tle,
最后实在没办法看的最小表示法,还有一点就是自己脑残,写成了ans=(slen%ans ? ans:slen/ans)不能整除明明是1啊!!
不过还是没搞懂为啥不能直接循环求最小,时间复杂度明明是一样的,最小表示法时间复杂度也是O(n)啊
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 10007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; const double g=10.0,eps=1e-9; const int N=1000000+5,maxn=(1<<18)-1,inf=0x3f3f3f3f; int Next[N],slen; string str; void getnext() { int k=-1; Next[0]=-1; for(int i=1;i<slen;i++) { while(k>-1&&str[k+1]!=str[i])k=Next[k]; if(str[k+1]==str[i])k++; Next[i]=k; } } int solve(bool flag) { int i=0,j=1,k=0; while(i<slen&&j<slen&&k<slen){ int t=str[(i+k)%slen]-str[(j+k)%slen]; if(!t)k++; else { if(flag)t>0 ? i=i+k+1:j=j+k+1; else t<0 ? i=i+k+1:j=j+k+1; if(i==j)j++; k=0; } } return min(i,j); } int main() { ios::sync_with_stdio(false); cin.tie(0); // cout<<setiosflags(ios::fixed)<<setprecision(2); while(cin>>str){ slen=str.size(); getnext(); int ans=slen-Next[slen-1]-1; ans=(slen%ans ? 1:slen/ans); cout<<solve(1)+1<<" "<<ans<<" "<<solve(0)+1<<" "<<ans<<endl; } return 0; }
hdu3374 kmp+最小表示法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。