Cod sursa(job #2458003)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 19 septembrie 2019 11:39:26
Problema Potrivirea sirurilor Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 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)
        {
            nn++;

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

            g<<i-2*s<<" ";
            o++;
            if(o>=1000)
                return 0;
        }
    }
    return 0;
}