Cod sursa(job #2480915)

Utilizator elenaisaiaElena Isaia elenaisaia Data 26 octombrie 2019 11:08:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 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()
{
    int pi=0;
   for(int i=2;i<=n;i++)
   {
       if(a[i]==a[pi+1])
       {
       pi++;
       prea[i]=pi;
       }
       else
       {
           pi=0;
           prea[i]=pi;
       }
   }
}
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]-n<<" ";
    return 0;
}