1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void bruteForce(string s,string p){//O(|P|·(|S|-|P|+1))
    int lenS = s.length(),lenP = p.length();//O(nm)
    for(int i=0;i<=lenS-lenP;i++){
        int flag=true;
        for(int j=0;P[j]!='\0';j++){
            if(s[i+j]!=p[j]){
                flag=false;
                break;
            }
        }
        if(flag){
            printf("%d\n",i);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void bruteForce(string s,string p){
    int lenS = s.length(),lenP = p.length();
    for(int i=0;i<=lenS-lenP;i++){
        int flag=true;
        if(s[i]==p[0]){
            for(int j=0;P[j]!='\0';j++){
            if(s[i+j]!=p[j]){
                flag=false;
                break;
            }
        }
        }
        if(flag){
            printf("%d\n",i);
        }
    }
}

 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

string s,p;//O(n+m)
int getNext(int x){
    for(int i=x;i>=1;i--){
        if(P.substr(0,i)==P.substr(x-i+1,i)){
            return i;
        }
    }
    return 0;
}
vector<int> getNxt(string s){
    int lenS = s.length();
    vector<int> p(lenS);
    for(int i=0;i<lenS;i++){
        p[i]=getNext(i);
    }
    return p;
}
void Search(){
    int tar=0,pos=0;
    int lenS = s.length(),lenP = p.length();
    while(tar<lenS){
        if(s[tar]==p[pos]){
            tar++,pos++;
        }else if(pos==0){
            pos = Nxt[pos-1];
        }else{
            tar++;
        }
        if(pos==lenP){
            printf("%d\n",tar-pos);
            pos = Nxt[pos-1];
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

vector<int> buildNxt(){
    vector<int> p;
    int x=1,now=0;
    p.push_back(0);
    while(x<lenP){
        if(p[now]==p[x]){
            now++;
            x++;
            p.push_back(now);
        }
        else if(now){
            now = p[now-1];
        }else{
            p.push_back(0);
            x++;
        }
    }
}