Cod sursa(job #3159831)

Utilizator ililogIlinca ililog Data 22 octombrie 2023 12:08:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>

#define NMAX 2000005
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pr[NMAX];
string A, B;

int main() {
    fin >> A >> B;
    A.push_back('#');
    
    int k = 0;
    for (int i = 1; i<A.size(); i++) {
        while (k != 0 && A[k] != A[i]) {
            k = pr[k-1];
        }
    
        if (A[k] == A[i]) {
            k++;
        } 
        pr[i] = k;
    }
    
    vector<int> ans;
    
    k = 0;
    for (int i = 0; i<B.size(); i++) {
        while (k != 0 && A[k] != B[i]) {
            k = pr[k-1];
        }
        if (A[k] == B[i]) {
            k++;
        }
        if (k >= A.size()-1) {
            ans.push_back(i - (A.size()-1) + 1);
        }
    }
    
    fout << ans.size() << '\n';
    for (int i = 0; i<min(1000, (int)ans.size()); i++) {
        fout << ans[i] << ' ';
    }
    fout << '\n';
    
    return 0;
}