Cod sursa(job #1810637)

Utilizator tqmiSzasz Tamas tqmi Data 20 noiembrie 2016 13:18:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005],B[2000005];
int sol[1005],q,N,M,cont,p[2000005];
void read()
{
    fin.getline(A+1,2000005);
    fin.getline(B+1,2000005);
    A[0]=' ';
    B[0]=' ';
    N=strlen(A)-1;
    M=strlen(B)-1;
    p[1]=0;
    q=0;
    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 solve()
{
    int q=0;
    for(int i=1;i<=M;i++)
    {
        while(q && A[q+1]!=B[i])
            q=p[q];
        if(A[q+1]==B[i])
            q++;
        if(q==N)
        {
            q=p[N];
            cont++;
            if(cont<=1000)
                sol[cont]=i-N;
        }
    }
    fout<<cont<<"\n";
    for(int i=1;i<=min(cont,1000);++i)
        fout<<sol[i]<<" ";
}
int main()
{
    read();
    solve();
    return 0;
}