Cod sursa(job #3255489)

Utilizator DragosDavidDavid Dragos Nicolae DragosDavid Data 10 noiembrie 2024 18:41:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int v[2231232];
int kal[2231232];
std::multiset<std::string> dv;
void build(string x){
    int i =1;
    v[0]=0;
    int j =0;
    while(i<x.length()){
            if(x[i]==x[j]){
                    j++;
                v[i]=j;
            i++;

            }
            else{
                if(j!=0){
                    j=v[j-1];
                }
                else{
                        v[i]=0;
                    i++;
                }
            }

    }

}
void solve(string x,string y,int &qq){
    int i =0 ;
    int j = 0;
    while(i<y.length()){
        if(y[i]==x[j]){
            i++;
            j++;
            if(j==x.length()){
                    qq++;
                    kal[qq-1]=i-j;
                j=v[j-1];
            }

        }
        else{
            if(j!=0){
                j=v[j-1];
            }
            else{
                i++;
            }
        }
    }
    fout<<qq<<'\n';


}
int main()
{
    int n;

    string pedo;
    string hamas;
    int qq=0;
    getline(fin,pedo);
    getline(fin,hamas);
    build(pedo);
    solve(pedo,hamas,qq);
    int i = 0;
    for(int i = 0;i<min(qq,1000);i++){
        fout<<kal[i]<<" ";
    }


    return 0;
}