Cod sursa(job #2857664)

Utilizator popescuadrianpopescuadrian popescuadrian Data 26 februarie 2022 00:49:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <string>

using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int rasp[2000005];
int main()
{
    int n,i,j,k;
    string a,b;
    char d,c;
    cin>>a>>b;
    int val=a.size();
    a='$'+a;
    a=a+'&';
    a=a+b;
    for(i=2;i<a.size();i++)
    {
        k=rasp[i-1];
        c=a[i];
        d=a[k+1];
        while(a[i]!=a[k+1] && k>=1)
        {
            k=rasp[k];
        }
        if(a[i]==a[k+1])
        {
            rasp[i]=k+1;
        }
        else
        {
            rasp[i]=0;
        }
    }
    int cnt=0;
    for(i=1;i<a.size();i++)
    {
       if(rasp[i]==val)
       {
           cnt++;
       }
    }
    cout<<cnt<<'\n';
    cnt=0;
    for(i=1;i<a.size();i++)
    {
        if(rasp[i]==val)
        {
            cout<<i-val+1-val-2<<" ";
            cnt++;
        }
    }
    return 0;
}