Cod sursa(job #2582625)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 17 martie 2020 10:29:11
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <string>
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

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

string a, b;
int pi[2000005];
vector<int> aparitii;

int main() {
    fin >> a >> b;
    int l1 = a.length(), l2 = b.length();

    int k = -1;
    for(int i = 1; i < l1; i++) {
        while(k > -1 && a[i] != a[k+1])
            k = pi[k];
        if(a[i] == a[k+1]) k++;
        pi[i] = k;
    }
    k = -1;
    for(int i = 0; i < l2; i++) {
        while(k > -1 && b[i] != a[k+1])
            k = pi[k];
        if(b[i] == a[k+1]) k++;
        if(k == l1-1)
            aparitii.push_back(i-l1+1);
    }
    fout << aparitii.size() << '\n';
    for(int i = 0; i < min(1000, int(aparitii.size())); i++)
        fout << aparitii[i] << ' ';
}