Cod sursa(job #2849728)

Utilizator PREDVCAPreduca Matei PREDVCA Data 15 februarie 2022 17:46:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
///#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;
const int SIZE = 2e6+10;

ifstream in ("strmatch.in");
ofstream cout ("strmatch.out");

char s[SIZE], sf[SIZE];
int sn, sfn;
int pre[SIZE], pos[SIZE];
int cnt;

void prep()
{
    int j=1;
    for(int i=2; i<=sfn; i++)
        if(sf[i]==sf[j]) {
            pre[i]=j;
            ++j;
        }
        else j=1;
}

void kmp()
{
    int j=0;
    for(int i=1; i<=sn; i++) {
        while(j && s[i]!=sf[j+1]) j=pre[j];
        if(s[i]==sf[j+1]) {
            ++j;
            if(j==sfn) {
                ++cnt;
                if(cnt<=1000) pos[cnt]=i-sfn;
            }
        }
    }
}

int main()
{
    in>>(sf+1)>>(s+1);
    sn = strlen(s+1);
    sfn = strlen(sf+1);
    prep();
    kmp();
    cout<<cnt<<'\n';
    for(int i=1; i<=min(1000, cnt); i++)
        cout<<pos[i]<<' ';
    return 0;
}