Cod sursa(job #1219837)

Utilizator tudi98Cozma Tudor tudi98 Data 15 august 2014 13:36:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

char A[2000005],B[2000005];
vector<int> Ans;
int pi[2000005];

void make_prefix(char A[]){

    int q = 0, N = strlen(A+1) - 1;
    pi[1] = 0;
    for(int i = 2; i <= N; i++){
        while(q && A[i] != A[q+1])
            q = pi[q];
        if(A[i] == A[q+1])
            q++;
        pi[i] = q;
    }
}

void match_KMP(char A[],char B[]){

    int N = strlen(A+1) - 1;
    int M = strlen(B+1) - 1;

    int q = 0;
    for(int i = 1; i <= M; i++){
        while(q && A[q+1] != B[i])
            q = pi[q];
        if(B[i] == A[q+1])
            q++;
        if(q == N)
            Ans.push_back(i-N);
    }
}

int main(){

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    fgets(A+1,sizeof(A),stdin);
    fgets(B+1,sizeof(B),stdin);

    make_prefix(A);
    match_KMP(A,B);

    int Matches = Ans.size();
    printf("%d\n",Matches);

    if(Matches > 1000) Matches = 1000;

    for(int i = 0; i < Matches; i++){
        printf("%d ",Ans[i]);
    }
}