Cod sursa(job #2480871)

Utilizator ana_maria_zotaZota Ana Maria ana_maria_zota Data 26 octombrie 2019 10:48:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN=2000000;
char a[MAXN],b[MAXN];
int n,m,p[MAXN],c,s[MAXN],nr,cc;
void prefix()
{
    for(int i=2; i<=n; i++)
    {
        while(a[i]!=a[c+1] && c!=0)
            c=p[c];
        if(a[i]==a[c+1])
            c++;
        p[i]=c;

    }
}
int pi=0;
void kmp()
{   pi=0;
    cc=0;
    for(int i=1;i<=m;i++)
    {   while(b[i]!=a[pi+1] && pi>0)
            pi=p[pi];
        if(b[i]==a[pi+1])
            pi++;
        if(pi==n)
            {   nr++;
                if(pi<=1000)
                    s[cc++]=i-n;

            }
    }
}
int main()
{
    fin.getline(a+1,MAXN);
    fin.getline(b+1,MAXN);
    n=strlen(a+1);
    m=strlen(b+1);
    prefix();
    kmp();
    fout<<nr<<"\n";
    for(int i=0;i<cc;i++)
        fout<<s[i]<<" ";

    return 0;
}