Cod sursa(job #2175121)

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

using namespace std;

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

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

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)
        {
            lenrez++;
            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=strlen(str1); n=strlen(str2);
    create_lps();
    KMP();
    if (lenrez>1000) fout<<1000<<'\n';
    else fout<<lenrez<<'\n';
    for (int i=1;i<=(lenrez>1000?1000:lenrez);++i) fout<<rez[i]<<" ";
    return 0;
}