Cod sursa(job #1726440)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 iulie 2016 00:16:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
///KMP
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2000005;

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

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

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

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

    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) {
            mt[++ans] = i - m;
            q = pi[m];
        }
    }

    printf("%d\n",ans);
    ans = min(ans, 1000); ///PRADUITORILOR!
    for(int i=1; i<=ans; ++i)
        printf("%d ",mt[i]);
    printf("\n");

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