Cod sursa(job #1311766)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 8 ianuarie 2015 16:19:04
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define pb push_back
#define max_dim 2000010

using namespace std;

vector<int> positions;

char a[max_dim], b[max_dim];
int next[max_dim];

int n, m, i, q, k;

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);

    scanf("%s%s", &a, &b);

    n=strlen(a+1); m=strlen(b+1);
    q=0; next[1]=0;

    for(i=2; i<=n; ++i)
    {
        while(a[i]!=a[q+1] && q!=0)
        q=next[q];

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

        next[i]=q;
    }
    q=0;
    for(i=1; i<m; ++i)
    {
        while(b[i]!=a[q+1] && q!=0)
        q=next[q];

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

        if(q==n)
        {
            if(positions.size()<=1000) positions.pb(i-n);
            q=next[q];
        }
    }

    printf("%d\n", positions.size());

    vector<int>::iterator it;

    for(it=positions.begin(); it!=positions.end(); ++it)
    printf("%d ", *it);

    return 0;
}