HDU 트레이닝 기록1: KMP

1、HDU 1711 Number Sequence
전송문
제목: 작은 꿰미가 큰 꿰미에서 처음으로 일치하는 위치를 구합니다.
문제풀이: 간단한 문자열 일치, KMP 템플릿 문제입니다.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_n=1e6+5;
const int max_m=1e4+5;

int w[max_n],s[max_m];
int T[max_m];
int t,n,m,ans;

inline void calc_T(){
    memset(T,0,sizeof(T));
    T[0]=-1;
    int j;
    for (int i=0;i<m;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}
inline void calc_ans(){
    ans=-1;
    int j=0;
    for (int i=0;i<n;++i){
        while (j!=-1&&w[i]!=s[j])
          j=T[j];
        ++j;
        if (j==m){
            ans=(i+1)-m+1;
            return;
        }
    }
}

int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;++i) scanf("%d",&w[i]);
        for (int i=0;i<m;++i) scanf("%d",&s[i]);
        calc_T();
        calc_ans();
        printf("%d
",ans);
    }
}

2、HDU 3336 Count the string
전송문
제목: 문자열의 모든 접두사가 문자열에 나타나는 횟수의 합을 구합니다.
문제풀이: 접두사는 뒤에 있는 문자의 어긋남에 나타난다. 사실은 모든 위치의 어긋남 개수의 합을 구하는 것이다.여기서 판단 조건은 짝짓기가 -1이 아니라는 것을 주의해야 한다. 짝짓기가 0이 되면 사실은 접두사 자체의 출현을 대표하기 때문이다.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_s=2e5+5;
const int Mod=10007;

char s[max_s];
int t,len,ans;
int T[max_s];

inline void calc_T(){
    memset(T,0,sizeof(T));
    T[0]=-1;
    int j;
    for (int i=0;i<len;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}
inline void calc_ans(){
    ans=0;
    int j;
    for (int i=1;i<=len;++i){
        j=T[i];
        while (j!=-1)
          j=T[j],ans=(ans+1)%Mod;
    }
}

int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d
",&len);
        gets(s);
        calc_T();
        calc_ans();
        printf("%d
",ans);
    }
}

3、HDU 3746 Cyclic Nacklace
전송문
제목: 문자열을 최소한 두 번 순환하는 최소한의 추가 문자의 개수를 주십시오.
문제풀이: 최소 순환절 = 문자열 길이 - 끝자리가 어긋납니다.최소 순환절에 부족한 개수를 구하는 것이 답이다.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_s=1e5+5;

char s[max_s];
int t,len,ans;
int T[max_s];

inline void calc_T(){
    T[0]=-1;
    int j;
    for (int i=0;i<len;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}
inline void calc_ans(){
    if (len%(len-T[len])==0&&len!=len-T[len]) ans=0;
    else ans=len-T[len]-(len%(len-T[len]));
}

int main(){
    scanf("%d
",&t);
    while (t--){
        gets(s);
        len=strlen(s);
        calc_T();
        calc_ans();
        printf("%d
",ans);
    }
}

4、HDU 1538 Period
전송문
제목: 한 사람당 1보다 큰 최대 순환 횟수를 구합니다.
문제풀이: 아니면 위의 결론을 이용하여: 최소 순환절 = 길이-말위 어긋남.한 분 한 분 일일이 열거하면 된다.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_n=1e6+5;

int n,num;
char s[max_n];
int T[max_n];

inline void calc_T(){
    T[0]=-1;
    int j;
    for (int i=0;i<n;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}

int main(){
    while (~scanf("%d
",&n)){
        if (!n) return 0;
        memset(T,0,sizeof(T));
        printf("Test case #%d
",++num);
        gets(s);
        calc_T();
        for (int i=2;i<=n;++i){
            if (i%(i-T[i])==0&&i!=i-T[i])
              printf("%d %d
",i,i/(i-T[i]));
        }
        putchar('
');
    }
}

5, HDU 2087 클립
전송문 얻기 힘든 중국어 문제...
제목: 작은 꿰미가 큰 꿰미 중 가장 많은 일치 횟수를 반복하지 않도록 하십시오.
문제풀이: KMP 클래식 모형으로 매번 찾은 후 어긋나지 않고 0으로 뛰면 됩니다.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_s=1005;

char W[max_s],s[max_s];
int T[max_s];
int len_s,len_W,ans;

inline void calc_T(){
    memset(T,0,sizeof(T));
    T[0]=-1;
    int j;
    for (int i=0;i<len_s;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}
inline void calc_ans(){
    int j=0;
    ans=0;
    for (int i=0;i<len_W;++i){
        while (j!=-1&&W[i]!=s[j])
          j=T[j];
        ++j;
        if (j==len_s){
            ans++;
            j=0;
        }
    }
}

int main(){
    while (~scanf("%s",W)){
        if (W[0]=='#') return 0;
        scanf("%s",s);
        len_s=strlen(s);
        len_W=strlen(W);
        calc_T();
        calc_ans();
        printf("%d
",ans);
    }
}

6、HDU 2594 Simpsons’Hidden Talents
전송문
제목: 가장 긴 공통 접두사를 구하십시오.
문제풀이: 두 개의 열을 연결한 다음에 어긋난 함수를 구하면 된다.마지막 비트와 두 문자열의 길이의 관계를 잘 판단하십시오.
code:

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int max_s=5e5+5;

char s[max_s],s2[max_s];
int T[max_s];
int l1,l2,len,ans;

inline void calc_T(){
    memset(T,0,sizeof(T));
    T[0]=-1;
    int j;
    for (int i=0;i<len;++i){
        j=T[i];
        while (j!=-1&&s[i]!=s[j])
          j=T[j];
        T[i+1]=++j;
    }
}
inline void calc_ans(){
    if (T[len]<=min(l1,l2)) ans=T[len];
    else ans=min(l1,l2);
}

int main(){
    while (~scanf("%s %s",s,s2)){
        l1=strlen(s);
        l2=strlen(s2);
        for (int i=0;i<l2;++i)
          s[l1+i]=s2[i];
        len=l1+l2;
        calc_T();
        calc_ans();
        for (int i=0;i<ans;++i)
          putchar(s[i]);
        if (ans) putchar(' ');
        printf("%d
",ans);
    }
}