Cod sursa(job #2737856)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 5 aprilie 2021 11:21:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX(2000005);
char a[NMAX], b[NMAX];
int pi[NMAX];
vector<int> vec;

int main()
{
    fin.getline(a + 1, NMAX - 3);
    fin.getline(b + 1, NMAX - 3);
    int n = strlen(a + 1);
    int m = strlen(b + 1);

    int k = 0;
    for(int i = 2; i <= n; ++i){
        while(k > 0 && a[i] != a[k + 1])
            k = pi[k];
        if(a[i] == a[k + 1])
            ++k;
        pi[i] = k;
    }

    k = 0;
    int cnt = 0;
    for(int i = 1; i <= m; ++i){
        while(k > 0 && a[k + 1] != b[i])
            k = pi[k];
        if(a[k + 1] == b[i])
            ++k;
        if(k == n){
            k = pi[k];
            ++cnt;
            if((int)vec.size() < 1000)
                vec.push_back(i - n);
        }

    }

    fout << cnt << '\n';
    for(auto it: vec)
        fout << it << ' ';
    return 0;
}