Cod sursa(job #2915921)

Utilizator raul41917raul rotar raul41917 Data 25 iulie 2022 23:01:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char txt[2000005];
char patt[2000005];
int lps[2000005];
int S[1005];
void construct(int L)
{
    int len=0;
    lps[0]=0;
    int i=1;
    while(i<L)
    {
        if(patt[i]==patt[len])
        {
            len++;
            lps[i]=len;
            i++;
        }else
        {
            if(len!=0)
                len=lps[len-1];
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
}
void KMP(int N,int M)
{
    int i=0;
    int j=0;
    while(i<N)
    {
        if(txt[i]==patt[j])
        {
            i++;
            j++;
            if(j==strlen(patt))
            {
                S[++S[0]]=i-j;
                j=lps[j-1];
            }
        }else
        {
            if(j!=0)
                j=lps[j-1];
            else
                i++;
        }

    }
}
int main()
{
    fi.getline(patt,2000001);
    fi.getline(txt,2000001);
    int lungime=strlen(patt);
    construct(lungime);
    KMP(strlen(txt),strlen(patt));
    fo<<S[0]<<"\n";
    if(S[0]>1000)
        S[0]=1000;
    for(int i=1;i<=S[0];i++)
        fo<<S[i]<<" ";
    return 0;
}