Cod sursa(job #3329426)

Utilizator todoranstefaniaTodoran Stefania todoranstefania Data 13 decembrie 2025 10:28:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir[2000005], subsir[2000005];
int p[2000005];
int main()
{
    fin.getline(subsir, 2000005);
    fin.getline(sir, 2000005);
    p[0]=0;
    int l=0;
    int n=strlen(subsir);
    int m=strlen(sir);
    int i=1;
    while(i<n){
        if(subsir[l]==subsir[i]){
            l++;
            p[i]=l;
            i++;
        }
        else{
            while(subsir[l]!=subsir[i] && l>0){
                l=p[l-1];
            }
            if(l>0){ //subsir[l]==subsir[i]                l++;
                p[i]=l;
                i++;
            }
            else{    ///l==0
                p[i]=0;
                i++;
            }
        }
    }
    m=strlen(sir);
    l=0;
    int cnt=0, sol[1005];
    for(int i=0; i<m; i++){
            while(subsir[l]!=sir[i] && l>0){
                l=p[l-1];
            }
            if(subsir[l]==sir[i])
                l++;
            if(l==n){
                if(cnt<1000)
                    sol[cnt]=i-n+1;
                cnt++;
                l=p[l-1];
            }
        }
        fout<<cnt<<"\n";
    for(int i=0; i<cnt && i<1000; i++)
        fout<<sol[i]<<" ";
    return 0;
}