Cod sursa(job #3255220)

Utilizator nistor_dora_valentinaNistor Dora Valentina nistor_dora_valentina Data 9 noiembrie 2024 18:25:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
int lga, lgb, i, j, lps[2000005], len, ans, rez[2000005];
int main()
{
    fin>>a>>b;
    lga=strlen(a);
    lgb=strlen(b);
    lps[0]=0;
    i=1;
    while(i<lga)
    {
        if(a[i]==a[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
            if(len!=0)
              len=lps[len-1];
            else
            {
                lps[i]=0;
                i++;
            }
    }
    i=0;
    j=0;
    while(i<lgb)
    {
        if(b[i]==a[j])
        {
            i++;
            j++;
            if(j==lga)
            {
                ans++;
                rez[ans]=i-lga;
                j=lps[j-1];
            }
        }
        else
        {
            if(j==0)
                i++;
            else
                j=lps[j-1];
        }
    }
    fout<<ans<<'\n';
    for(i=1; i<=ans; i++)
        fout<<rez[i]<<" ";

    return 0;
}