Cod sursa(job #2824653)

Utilizator marcumihaiMarcu Mihai marcumihai Data 2 ianuarie 2022 21:02:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

char a[2000005];
char b[2000005];
int s[2000005];
int nr;
int n;
int m;
int rez[2000005];





int main()
{
    f>>(a);
    f>>(b);
    int n=strlen(a);
    int m=strlen(b);

    --n;
    --m;

    int i=0;
    int j=1;

    while(i<=j && j<=n)
    {


        if(a[i]==a[j])
        {
            s[j]=s[j-1]+1;
            ++i;
            ++j;
        }
        else
        {
            while(a[i]!=a[j] && i!=0)
            {
                i=s[i-1];
            }
            if(a[i]==a[j])
            {
                s[j]=s[i]+1;
                ++i;
                ++j;
            }
            else
            {
                s[j]=0;
                ++j;
            }

        }
    }

    i=0;
    j=0;

    while(i<=j && j<=m)
    {
        if(a[i]==b[j] && i<=n)
        {
            if(j!=0 && i!=0)
                rez[j]=rez[j-1]+1;
            else if(j==0 || i==0)
                rez[j]=1;

            ++i;
            ++j;
        }
        else
        {
            while(a[i]!=b[j] && i!=0)
            {
                i=s[i-1];
            }
            if(a[i]==b[j])
            {
                rez[j]=rez[i]+1;
                ++i;
                ++j;
            }
            else
            {
                rez[j]=0;
                ++j;
            }
        }
        if(i==n)
        {
            i=s[i]+1;
        }
    }
    int cont=0;
    for(int i=0;i<=m;++i)
        if(rez[i]==n+1)
            ++cont;



    g<<cont<<"\n";
    int nr=0;
    for(int i=0;i<=m;++i)
    {
        if(rez[i]==n+1 && nr<1000)
        {
            g<<i-n<<" ";
            ++nr;
        }
    }

    return 0;
}