hdu3374 最大最小表示法 +kmp
2024-10-16 13:28:20
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=;
int MinRepresstation(char * S, int len ) {
int i = , j = , k = ;
while(i < len && j < len)
{
k = ;
while(k < len && S[(i + k)%len] == S[(j + k)%len])
k++;
if(k >= len)
break;
if(S[(i + k)%len] > S[(j + k)%len])
i = max(i + k + , j + );
else
j = max(i + , j + k + );
}
return min(i ,j);
}
int MaxRepresstation(char * S, int len ) {
int i = , j = , k = ;
while(i < len && j < len)
{
k = ;
while(k < len && S[(i + k)%len] == S[(j + k)%len])
k++;
if(k >= len)
break;
if(S[(i + k)%len] > S[(j + k)%len])
j = max(i + , j + k + );
else
i = max(i + k + , j + );
}
return min(i ,j);
}
char s[maxn];
char s1[maxn],s2[maxn];
void getFail(char *P, int *f, int m)
{
f[]=; f[]=;
for(int i=; i<m; i++)
{
int j=f[i];
while(j&&P[i]!=P[j])j=f[j];
f[i+]=P[i]==P[j]?j+:;
}
}
int find(char *T,char *P, int *f,int n, int m)
{
getFail(P,f,m);
int j=;
int num=;
for(int i=; i<n-; i++)
{
while(j&&P[j]!=T[i])j=f[j];
if(P[j]==T[i])j++;
if(j==m){
num++; j=f[j];
}
}
return num;
}
int F[maxn]; int main()
{ while(gets(s))
{ int len=strlen(s);
int d1=MinRepresstation(s,len);
int d2=MaxRepresstation(s,len);
for(int i = ; i < len ; i ++)
s[ i + len ] = s[ i ];
for(int i=; i<len; i++)
{
s1[i]=s[(i+d1)%len];
s2[i]=s[(i+d2)%len];
}
int ans1=find(s,s1,F,len*,len);
int ans2=find(s,s2,F,len*,len);
printf("%d %d %d %d\n",d1+,ans1,d2+,ans2);
} return ;
}
最新文章
- js类型转换
- css样式
- NK3C系统中ID的汉语名称
- 新版WampServer项目路径前面没有localhost
- 20145320《Java程序设计》第4周学习总结
- Delphi 打印
- source command not found in sh shell解决办法
- BZOJ 2463: [中山市选2009]谁能赢呢?[智慧]
- C/C++语言简介之语法结构
- NodeJS Addon 多线程通信
- Python学习过程中各个难点---数据类型篇
- mysql数据库可以远程连接或者说用IP地址可以访问
- Java学习笔记11(this,super)
- Top 10 Best Free Netflow Analyzers and Collectors for Windows
- C++中的也能使用正则表达式----转载
- 修改IP
- 排序算法之堆排序(Heapsort)解析
- Activity的setResult方法
- LoadRunner FAQ
- Asp.Net MVC Identity 2.2.1 使用技巧(七)