Cod sursa(job #1954929)

Utilizator LizaSzabo Liza Liza Data 5 aprilie 2017 18:54:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax=2000005;
int N,M,q,P[NMax],Sol[1005],k;
char A[NMax],B[NMax];

void Read()
{
    fin.getline(A+1,NMax);
    fin.getline(B+1,NMax);
     A[0]=B[0]=' ';
    N = strlen(A);
    M = strlen(B);
    N--;
    M--;
}

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

        if(A[i]==A[q+1])
        {
           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)
       {
           k++;
           if(k<=1000)
           {
               Sol[k]=i-N;
           }
           q=P[q];
       }
    }
    fout<<k<<"\n";
    for(int i=1;i<=min(k,1000);++i)
    {
        fout<<Sol[i]<<" ";
    }
    fout<<"\n";
}


int main()
{
   Read();
   Make_prefix();
   KMP();

    return 0;
}