Cod sursa(job #2849395)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 15 februarie 2022 09:17:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
///#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

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

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

char s1[SIZE], s2[SIZE];
int s1n, s2n;
int pre[SIZE];
int cnt;
vector <int> rez;

void getPre()
{
    int i, j;
    for(j=2, i=1; j<=s2n; j++)
        if(s2[j]==s2[i]) {
            pre[j] = i++;
        }
        else {
            while(i && s2[i]!=s2[j]) i=pre[i];
            if(!i) i++;
            if(s2[j]==s2[i]) pre[j] = i++;
        }
}

int main()
{
    cin>>(s2+1)>>(s1+1);
    s1n = strlen(s1+1);
    s2n = strlen(s2+1);
    getPre();
    int i, j;
    for(i=1, j=0; i<=s1n; i++) {
        if(s1[i]==s2[j+1]) {
            ++j;
            if(j==s2n) {
                ++cnt;
                j=pre[j];
                if(rez.size()<1000) rez.push_back(i-s2n);
            }
        }
        else {
            while(j && s1[i]!=s2[j+1]) j=pre[j];
            if(s1[i]==s2[j+1]) ++j;
        }
    }
    cout<<cnt<<'\n';
    for(auto i : rez) cout<<i<<' ';
    return 0;
}