Cod sursa(job #981540)

Utilizator StanAndreiAndrei Stan StanAndrei Data 7 august 2013 14:36:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <string.h>
#include <vector>

#define NMAX 2000005

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[NMAX],B[NMAX];
int NXT[NMAX],NR;

vector<int> Q;

int LENA,LENB;

void read()
{
    fin.getline(A,2000005);
    fin.getline(B,2000005);

    LENA=strlen(A);
    LENB=strlen(B);
}

void next()
{
    int k=-1,x;

    for (x=1;x<=LENA;x++)
    {
        while (k>0 && A[k+1]!=A[x])
            k=NXT[k];
        if (A[k+1]==A[x])
            k++;
        NXT[x]=k;
    }
}

void solve()
{
    int i,x=-1;
    next();
    for (i=0;i<LENB;i++)
    {
        while (x>0 && A[x+1]!=B[i])
            x=NXT[x];
        if (A[x+1]==B[i])
            x++;
        if (x==LENA-1 && NR<1000)
        {
            Q.push_back(i-LENA+1);
            NR++;
            x=NXT[x];
        }
    }

    fout<<NR<<'\n';
    for (i=0;i<Q.size();i++)
        fout<<Q[i]<<" ";
}

int main()
{
    read();
    solve();

    fin.close();
    fout.close();

    return 0;
}