Cod sursa(job #1252777)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 31 octombrie 2014 11:38:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int n, m, i, k, t, pi[2000005], d[2000005];
char a[2000005], b[2000005];
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(a+1);
    gets(b+1);
    n=strlen(a+1);
    m=strlen(b+1);

    k=0;
    pi[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&a[k+1]!=a[i])
            k=pi[k];

        if(a[k+1]==a[i])
            k++;

        pi[i]=k;
    }

    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&a[k+1]!=b[i])
            k=pi[k];

        if(a[k+1]==b[i])
            k++;

        d[i]=k;
        if(k==n) t++;
    }

    printf("%d\n", t);
    k=0;
    for(i=1;i<=m;i++)
        if(d[i]==n)
        {
            k++;
            printf("%d ", i-n);
            if(k==1000) break;
        }

    return 0;
}