Cod sursa(job #2458010)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 19 septembrie 2019 11:49:04
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
string a;
string b;
long long kmp[4000002];
int main()
{
    f>>a>>b;
    string c= a+b;
    long long n=c.size();
    kmp[0]=-1;
    kmp[1]=0;
   // g<<n;
   long long x=-1;
    for(long long i=1;i<=n;++i)
    {
       // for(int j=0;j<i;++j)
       //     g<<c.at(j);
      //  g<<" ";

        while(x>-1 && c[x]!=c[i-1])
        {
            x=kmp[x];
        }
        ++x;
        kmp[i]=x;
       // g<<kmp[i]<<"\n";
    }

    long long s=a.size();
    long long nn=0;
    for(long long i=2*s;i<=n;++i)
    {

        if(kmp[i] >= s)
        {
            int r=kmp[i];
            while(r>s)
            {
                r=kmp[r];
                if(r==s)
                    break;
            }
            if(r==s)
            {
                 nn++;
            }
        }
    }
    g<<nn<<"\n";
    long long o=0;
    for(long long i=2*s;i<=n;++i)
    {

        if(kmp[i] >= s)
        {
            int r=kmp[i];
            while(r>s)
            {
                r=kmp[r];
                if(r==s)
                    break;
            }
            if(r==s)
            {
                 g<<i-2*s<<" ";
                o++;
                if(o>=1000)
                    return 0;
            }
        }
    }
    return 0;
}