Cod sursa(job #2175318)

Utilizator aditoma2001Toma Adrian aditoma2001 Data 16 martie 2018 16:34:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

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

string str1,str2;
int k=1,len,n,m,lps[2000001],i,j,rez[2000001];

void create_lps()
{
    lps[0]=0;
    while (k<m)
    {
        if (str1[k]==str1[len])
        {
            len++;
            lps[k]=len;
            k++;
        }
        else
        {
            if (len>0) len=lps[len-1];
            else lps[k]=0,k++;
        }
    }
}

void KMP()
{
    k=1;
    while (i<n)
    {
        if (str2[i]==str1[j]) i++,j++;
        if (j==m)
        {
            rez[k++]=i-j;
            j=lps[j-1];
        }
        else
        {
            if(i<n&&str1[j]!=str2[i])
            {
                if (j!=0)
                {
                    j=lps[j-1];
                }
                else i++;
            }
        }
    }
}

int main()
{
    fin>>str1>>str2;
    m=str1.length(); n=str2.length();
    create_lps();
    KMP();
    k--;
    if (k>1000) k=1000;
    fout<<k<<'\n';
    for (int i=1;i<=k;++i) fout<<rez[i]<<" ";
    return 0;
}