Cod sursa(job #2825334)

Utilizator marcumihaiMarcu Mihai marcumihai Data 4 ianuarie 2022 16:01:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 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;
    s[0]=-1;
    while(i<=j && j<=n)
    {
        if(a[i]==a[j])
        {
            s[j]=i;
            ++i;
            ++j;
        }
        else
        {
            --i;
            while(a[i+1]!=a[j] && i!=-1)
            {
                i=s[i];
            }
            ++i;
            if(a[i]==a[j])
            {
                s[j]=i;
                ++i;
                ++j;
            }
            else
            {
                s[j]=-1;
                ++j;
            }

        }
    }


    i=0;
    j=0;

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

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


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

    return 0;
}