2016年11月5日 星期六

TIOJ 1306 - 字串中的字串

http://tioj.infor.org/problems/1306

 裸裸KMP
不過寫幾次忘幾次
後來從頭到尾都在背code了(((
詳細可參考演算法筆記之類的
不過我的寫法有點不太一樣就是了
雖然只是微妙的差別(#



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define MS0(x) memset((x),0,sizeof(x))

int F[10005];

int KMP(string &s,string &t){
    if(t.length()>s.length())return 0;
    MS0(F);
    int cnt=0;
    F[0]=-1;F[1]=0;
    for(int i=1,j=1;i<(int)t.length();++i,j=i){
        while(t[i]!=t[F[j]] && j)j=F[j];
        F[i+1]=F[j]+1;
    }
    for(int i=0,j=0;i+j<(int)s.length();j++){
        if(s[i+j]==t[j]){
            if(j==(int)t.length()-1){
                cnt++;
                i+=t.length()-F[j+1];
                j-=t.length()-F[j+1];
            }
        }
        else{
            i+=j-F[j];
            j-=j-F[j]+1;
            if(j<-1)j=-1;
        }
    }
    return cnt;
}

int main(){
    // cin.tie(0);
    ios_base::sync_with_stdio(0);
    int ts;cin>>ts;while(ts--){
        string a;cin>>a;
        int n;cin>>n;for(int i=0;i<n;++i){
            string c;cin>>c;
            cout<<KMP(a,c)<<'\n';
        }
    }
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)