Cod sursa(job #2980607)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 16 februarie 2023 18:01:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char v[4000010];
int pi[4000010],rez[1010];
int main()
{
    int n,n1,i,ct;
    char ch;
    cin.get(ch);
    n=0;
    while (ch!='\n')
    {
        n++;
        v[n]=ch;
        cin.get(ch);
    }
    n1=n;
    n++;
    v[n]='#';
    for (i=2; i<=n-1; i++)
    {
        pi[i]=pi[i-1];
        while (pi[i]!=0 && v[pi[i]+1]!=v[i])
            pi[i]=pi[pi[i]];
        if (v[pi[i]+1]==v[i])
            pi[i]++;
    }
    pi[n]=0;
    i=n;
    n++;
    ct=0;
    while (cin>>v[n])
    {
        i++;
        pi[i]=pi[i-1];
        while (pi[i]!=0 && v[pi[i]+1]!=v[n])
            pi[i]=pi[pi[i]];
        if (v[pi[i]+1]==v[n])
            pi[i]++;
        if (pi[i]==n1)
        {
            ct++;
            if (ct<=1000)
                rez[ct]=i-2*n1-1;
        }
        n++;
    }
    cout<<ct<<"\n";
    if (ct<=1000)
        for (i=1; i<=ct; i++)
            cout<<rez[i]<<" ";
    else
        for (i=1; i<=1000; i++)
            cout<<rez[i]<<" ";
    return 0;
}