Cod sursa(job #2866284)

Utilizator Emilia23Dobra Emilia Emilia23 Data 9 martie 2022 16:02:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include<bits/stdc++.h>
#define SIZE 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char x[SIZE],y[SIZE];
int l[SIZE],sol[SIZE],nr,n,m;

void prefix()
{
    int k=0,i;
    for(i=2;i<=n;i++)
    {
        k=l[i-1];
        while(k>0 && x[i]!=x[k+1])
        {
            k=l[k];
        }
        if(x[i]==x[k+1])k++;
        l[i]=k;
    }
}
void kmp()
{
    int k=0,i;
    for(i=1;i<=m;i++)
    {
        while(k>0 && y[i]!=x[k+1])
        {
            k=l[k];
        }
        if(y[i]==x[k+1])k++;
        if(k==n)sol[++nr]=i-n;
    }
    g<<nr<<'\n';
    for(i=1;i<=min(nr,1000);i++)
        g<<sol[i]<<' ';
}

int main()
{
    f.getline(x+1,SIZE);
    f.getline(y+1,SIZE);
    n=strlen(x+1);
    m=strlen(y+1);
    prefix();
    kmp();
    return 0;
}