Cod sursa(job #2480892)

Utilizator elenaisaiaElena Isaia elenaisaia Data 26 octombrie 2019 10:56:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr=0;
int c[1002];
char a[2000001],b[2000001];
int prea[2000005];
int k;
int n;
int m;
void prelucrare()
{
    for(int i=2; i< n+1; i++)
    {
        k=1;

        if(a[i]==a[1])
        {

            int j;
            prea[i]=k++;
            for( j = i+1;j<n+1&&a[j]==a[k];j++)
                prea[j]=k++;
            i=j;
        }
    }
}
void KMP()
{
int pi=0;
for(int i=1;i<=m;i++)
{
    while(pi>0 &&b[i]!=a[pi+1])
    {
        pi=prea[pi];
    }
    if(b[i]==a[pi+1])
    {
        pi+=1;
    }
    if(pi==n)
    {
        if(nr<1000)
            c[nr++]=i;
        else
            nr++;
    }
}
}

int main()
{

    fin.getline(a+1,2000005);
    fin.getline(b+1,2000005);
    n=strlen(a+1);
    m=strlen(b+1);
    prelucrare();
    KMP();
       fout<<nr<<'\n';
        int p;
        if(nr>1000)
            p=1000;
            else p=nr;
        for(int i=0;i<p;i++)
            fout<<c[i]-strlen(a+1)<<" ";
    return 0;
}