Cod sursa(job #2435477)

Utilizator Adrian_Popescu311Popescu Adrian Adrian_Popescu311 Data 4 iulie 2019 09:43:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream fi("strmatch.in");

long int lps[2000010];
char a[2000010];
char b[2000010];
long int n,m;
long int nr;

long int vec[2000010];

void cit()
{
    fi>>a>>b;
}

void lpss()
{
    long int i,j;
    i=0;
    j=1;

    n=strlen(a);
    m=strlen(b);

    lps[0]=0;

    while(j<n)
        if(a[i]==a[j])
    {
        i++;
        lps[j]=i;
        j++;
    }
        else
            if(i!=0)
                i=lps[i-1];
            else
            {
                lps[j]=0;
                j++;
            }

}

void KMP()
{
    long int i,j;

    i=j=0;

    lpss();

    while(i<m)
        {if(a[j]==b[i])
            {i++;
            j++;}

        if(j==n)
        {
            vec[++nr]=i-j;
            j=lps[j-1];
        }
        else
            if(i<m&&a[j]!=b[i])
                if(j!=0)
                    j=lps[j-1];
                else
                    i++;}



}

int main()
{

    fi>>a>>b;

    lpss();

    KMP();

    cout<<nr<<'\n';

    for(long int i=1;i<=nr;i++)
        cout<<vec[i]<<" ";

    return 0;
}