Cod sursa(job #1726431)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 7 iulie 2016 23:34:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
///KMP
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2000005;

int  pi[NMAX];
char  p[NMAX],
      t[NMAX];

int main(void) {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    vector<int> ans;
    int n, m, q;

    scanf("%s%s",p+1,t+1);

    n   = strlen(t+1);
    m   = strlen(p+1);

    if(n < m) {
        printf("%d\n",0);
        fclose(stdin);
        fclose(stdout);
    }

    pi[1] = 0;
    for(int i=2, k=0; i<=m; ++i) {
        while(k>0 && p[k+1]!=p[i])
            k = pi[k];
        if(p[k+1]==p[i])
            ++k;
        pi[i] = k;
    }

    q = 0;
    for(int i=1; i<=n; ++i) {
        while(q>0 && p[q+1]!=t[i])
            q = pi[q];
        if(p[q+1]==t[i])
            ++q;
        if(q==m)
            ans.push_back(i-m);
    }

    printf("%d\n",ans.size());
    for(auto i:ans)
        printf("%d ",i);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}