Cod sursa(job #3040633)

Utilizator Gruiagruiagruia Gruia Data 30 martie 2023 10:58:25
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[100001];
string ahoy,corasick;
vector<int> rez;
int main()
{
    int n,m,i,j,len=0,c=0;
    fin>>ahoy>>corasick;
    n=ahoy.size();
    lps[0]=0;
    i=1;
    while(i<n)
    {
        while(ahoy[i]!=ahoy[len]&&len>0)
        {
            len=lps[len-1];
        }
        if(ahoy[i]==ahoy[len])
            len++;
        lps[i++]=len;
    }
    m=corasick.size();
    i=0,j=0;
    while(i<m)
    {
        while(corasick[i]!=ahoy[j]&&j>0)
            j=lps[j-1];
        if(corasick[i]==ahoy[j])
            j++;
        i++;
        if(j==n)
        {
            c++;
            if(c<=1000)
                rez.push_back(i-n);
        }
    }
    fout<<c<<'\n';
    for(i=0;i<rez.size();i++)
        fout<<rez[i]<<' ';
    return 0;
}