Cod sursa(job #1311769)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 8 ianuarie 2015 16:21:26
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <fstream>
#define pb push_back
#define max_dim 2000010

using namespace std;

vector<int> positions;

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

int n, m, i, q, k;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f>>a+1; f>>b+1;

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

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

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

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

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

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

    g<<positions.size()<<"\n";

    vector<int>::iterator it;

    for(it=positions.begin(); it!=positions.end(); ++it)
    g<<*it<<" ";

    return 0;
}