Cod sursa(job #2722499)

Utilizator DragosGavrusDragos Gavrus DragosGavrus Data 12 martie 2021 21:42:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

int lps[2000003],ap[1003],ans,n,m;

void formare_lps(char pattern[])
{
    int index=0;
    for(int i=1;i<n;)
    {
        if(pattern[index]==pattern[i])
        {
            lps[i]=index+1;
            index++;
            i++;
        }
        else if(index!=0)
            index=lps[index-1];
        else
        {
            lps[i]=0;
            i++;
        }
    }
}

void KMP (char text[],char pattern[])
{
    int i=0,j=0;
    while(i<m)
    {
        if(text[i]==pattern[j])
        {
            i++;
            j++;
        }
        else if(j!=0)
        {
            j=lps[j-1];
        }
            else
            {
                i++;
            }

        if(j==n)
        {
            ans++;
            if(ans<=1000)
                ap[ans]=i-n;
        }
    }
}


char text[2000003],pattern[2000003];

int main()
{
    f.getline(pattern,2000003);
    f.getline(text,2000003);

    n=strlen(pattern);
    m=strlen(text);

    formare_lps(pattern);
    KMP(text,pattern);
    g<<ans<<"\n";
    for(int i=1;i<=min(ans,1000);i++)
        g<<ap[i]<<" ";
    return 0;
}