Cod sursa(job #1199215)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 18 iunie 2014 16:24:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 2000002
char s[MAX], p[MAX];
int pi[MAX], n, m, sol[1001], nsol;
void prefix();
void kmp();
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s\n", p+1, s+1);
    n = strlen(s+1); m = strlen(p+1);
    prefix();
    kmp();
    printf("%d\n", nsol);
    if(nsol>1000) nsol = 1000;
    for(int i=1; i<=nsol; i++) printf("%d ", sol[i]);
    return 0;
}
void kmp(){
    int q=0;
    for(int i=1; i<=n; i++){
        while(q>0 and p[q+1]!=s[i])
            q = pi[q];
        if(p[q+1]==s[i])
            q++;
        if(q==m){
            nsol++;
            if(nsol<=1000) sol[nsol] = i-m;
            q = pi[q];
        }
    }
}
void prefix(){
    int q, k;
    k = pi[1] = 0;
    for(q=2; q<=m; q++){
        while(k>0 and p[k+1]!=p[q])
            k = pi[k];
        if(p[k+1]==p[q]) k++;
        pi[q] = k;
    }
}