Cod sursa(job #2656432)

Utilizator Gheorghita_VladGheorghita Vlad Gheorghita_Vlad Data 7 octombrie 2020 18:39:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int lps[2000005],v[2000005];
char A[2000005],B[2000005];
void BuildLPS()
{
    int i,len;
    len=0;
    lps[0]=0;
    i=1;
    while (i<strlen(B))
    {
        if (B[i]==B[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if (len!=0)
            {
                len=lps[len-1];
            }
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
}
void KMP()
{
    int i,j,k;
    i=j=k=0;
    while (i<strlen(A))
    {
        if (A[i]==B[j])
        {
            i++;
            j++;
        }
        if (j==strlen(B))
        {
            v[++k]=i-j;
            j=lps[j-1];
        }
        else if (i<strlen(A) && B[j]!=A[i])
        {
            if (j)
                j=lps[j-1];
            else i++;
        }
    }
    g<<k<<'\n';
    for (i=1;i<=k && i<=1000;i++) g<<v[i]<<" ";
}
int main()
{
    f>>B;
    f>>A;
    BuildLPS();
    KMP();
    return 0;
}