Cod sursa(job #2972668)

Utilizator andiRTanasescu Andrei-Rares andiR Data 29 ianuarie 2023 23:55:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Mmax=2000000;

int ap, v[1000], pi[Mmax];
string s, p;

inline void inPI(string &p){
    int stare=0;
    pi[0]=0;
    for (int i=1; i<p.size(); i++){
        while (stare!=0 && p[i]!=p[stare])
            stare=pi[stare-1];
        if (p[i]==p[stare])
            stare++;
        pi[i]=stare;
    }
}
inline void KMP(string &s, string &p){
    inPI(p);
    int stare=0;
    for (int i=0; i<s.size(); i++){
        while (stare!=0 && s[i]!=p[stare])
            stare=pi[stare-1];
        if (s[i]==p[stare])
            stare++;
        if (stare==p.size()){
            ap++;
            if (ap<=1000)
                v[ap-1]=i-p.size()+1;
        }
    }
}
int main()
{
    fin>>p>>s;
    KMP(s, p);
    fout<<ap<<'\n';
    ap=min(ap, 1000);
    for (int i=0; i<ap; i++)
        fout<<v[i]<<' ';
    return 0;
}