Cod sursa(job #2307046)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 23 decembrie 2018 16:57:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int L=2000001;
int sol[1001], lps[L+1];
char txt[L+1], pat[L+1];
int Nsol, n, m;

void LPS(char *pat, int m)
{
    /// Calculez LPS
    int len=0;
    lps[0]=0;
    int i=1;
    while(i<m)
    {
        if(pat[i]==pat[len])
        {
            ++len;
            lps[i]=len;
            ++i;
        }
        else /// pat[i]!=pat[len]
        {
            if(len!=0) len=lps[len-1];
            else
            {
                lps[i]=0;
                ++i;
            }
        }
    }
}

void KMP_search(char *txt, char *pat)
{
    n=strlen(txt);
    m=strlen(pat);
    LPS(pat, n);

    int i=0, j=0;
    while(i<n)
    {
        if(txt[i]==pat[j])
        {
            ++j;
            ++i;
        }
        if(j==m)
        {
           ++Nsol;
           if(Nsol<=1000) sol[Nsol]=i-j;
           j=lps[j-1];
        }
        else if(i<n && pat[j]!=txt[i])
        {
            if(j!=0) j=lps[j-1];
            else ++i;
        }
    }
}

int main()
{
    fin.getline(pat, L);
    fin.getline(txt, L);
    Nsol=0;
    KMP_search(txt, pat);
    fout<<Nsol<<"\n";
    for(int i=1; i<=min(Nsol, 1000); ++i) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}