Cod sursa(job #1666033)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 27 martie 2016 16:41:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstring>
#define NM 2000000

using namespace std;

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

int V[1005];

char A[NM], B[NM];
int Pi[NM], n, m, ori;

void BuildPi()
{
    Pi[0]=0;
    int i, j=0;
    for (i=1; i<n; i++)
    {
        while (j>0 && A[i]!=A[j])
        {
            j=Pi[j-1];
        }
        if (A[i]==A[j])
        {
            j++;
        }
        Pi[i]=j;
    }
}

void KMP()
{
    int i, j=0;
    for (i=0; i<m; i++)
    {
        while (j>0 && A[j]!=B[i])
        {
            j=Pi[j-1];
        }
        if (B[i]==A[j])
        {
            j++;
        }
        if (j==n)
        {
            ori++;
            V[ori]=i-n+1;
            if (ori==1000)
                return;
        }
    }
}

int main()
{
    int i;
    fin.getline(A, NM);
    fin.getline(B, NM);
    n=strlen(A);
    m=strlen(B);
    BuildPi();
    KMP();
    fout<<ori<<'\n';
    for (i=1; i<=ori; i++)
    {
        fout<<V[i]<<" ";
    }
    return 0;
}