大致题意:
给出一个字符串,求出其第一个最小表示和最大表示的位置,并分别求出最小表示的个数和最大表示的个数。
大致思路:
最小表示法+KMP扩展出的最小重复子串,一顿乱搞即可。本来打算用后缀数组,但是看数据量达到了1000000,还是作罢了~~囧
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
//最小表示
int minexp(char *s,int x) {
int i=0,j=1,k=0,t;
while(i<x&&j<x&&k<x) {
t=s[(i+k)%x]-s[(j+k)%x];
if(t==0) k++;
else {
if(t>0) i+=k+1;
else j+=k+1;
if(i==j) j++;
k=0;
}
}
return i<j?i:j;
}
//最大表示
int maxexp(char *s,int x) {
int i=0,j=1,k=0,t;
while(i<x&&j<x&&k<x) {
t=s[(i+k)%x]-s[(j+k)%x];
if(t==0) k++;
else {
if(t<0) i+=k+1; //这里是区别
else j+=k+1;
if(i==j) j++;
k=0;
}
}
return i<j?i:j;
}
int main(){
int ans,i,j,a,b;
while(scanf("%s",pat)!=EOF){
lenp=strlen(pat);
get_next();
a=minexp(pat,lenp);
b=maxexp(pat,lenp);
int l=(lenp-1)-next[lenp-1];
if(lenp%l==0){
ans=lenp/l;//cout<<lenp/l<<endl;;
}
else{
ans=1;//printf("1\n");
}
printf("%d %d %d %d\n",a+1,ans,b+1,ans);
}
return 0;
}
//h 3374
分享到:
相关推荐
KMP算法学习&总结 1、传统的字符串匹配算法 /* * 从s中第sIndex位置开始匹配p * 若匹配成功,返回s中模式串p的起始index * 若匹配失败,返回-1 */ int index(const std::string &s, const std::string &p, ...
KMP算法,详细的解释了如何去匹配字符串。做成了实验报告,希望给大家帮助。
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
《数据结构》用C语言实现的模式匹配KMP算法,可用于求出子串在主串中的位置。
我自己用C语言写的,用了KMP算法,实现了从文件中查找字符的功能。
让你迅速透彻的理解KMP算法! [1] http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm [KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of ...
KMP算法源代码 C语言 KMP算法源代码 C语言 KMP C语言
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP algorithm for matching string problem
KMP算法+全网最最最详细的代码注释,逐行注释,一看就懂,Code::Bclocks亲测完美运行!
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
C语言字符串模式配KMP算法,包含了C的算法!
void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
KMP算法
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
模式匹配,KMP算法,string-match-kmp-master.zip
kmp算法用C语言编写+最短路径ShortestPath_DIJ编码
KMP算法的java实现,KMP详细解说请移步:https://blog.csdn.net/Michaelia_hu/article/details/100888201
...关于string的小结 kmp extend_kmp ac+trie 后缀数组