Cod sursa(job #1953959)

Utilizator edi_laitinLaitin Eduard edi_laitin Data 5 aprilie 2017 09:35:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000005

using namespace std;

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

char A[Nmax],B[Nmax];
int P[Nmax],q,N,M,sol[1005],n;

void Read()
{
    fin.getline(A+1,Nmax);
    fin.getline(B+1,Nmax);

    A[0]=B[0]=' ';

    N = strlen(A);  N--;
    M = strlen(B);  M--;
}

void Precalculate()
{
    for(int i=2; i<=N; i++)
    {
        while(q && A[q+1]!=A[i])
            q=P[q];
        if(A[q+1]==A[i])
            q++;
        P[i]=q;
    }
}

void KMP()
{
   q=0;

   for(int i=1; i<=M; i++)
   {
       while(q && B[i]!=A[q+1])
            q=P[q];
       if(B[i]==A[q+1])
            q++;
       if(q==N)
       {
           q=P[q];
           n++;
           if(n<=1000)
           sol[n]=i-N;
       }
   }
}

void Print()
{
    fout<<n<<"\n";
    for(int i=1; i<=min(n,1000); i++)
        fout<<sol[i]<<" ";
}

int main()
{
    Read();
    Precalculate();
    KMP();
    Print();

    return 0;
}