Cod sursa(job #3238940)

Utilizator Allie28Radu Alesia Allie28 Data 31 iulie 2024 16:40:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <climits>

using namespace std;

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

const int LMAX = 2000005;

char a[LMAX], b[LMAX];
int pi[LMAX];
int n, m;

//pi[i] --> lungimea celui mai lung prefix sufix

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

int main() {
    fin.get(a + 1, LMAX);
    fin.get(b + 1, LMAX);
    n = strlen(a + 1);
    m = strlen(b + 1);
    Pi();
    int k = 0;
    vector<int> sol;
    for (int i = 2; i < m; i++) {
        while (k && a[k + 1] != b[i]) {
            k = pi[k];
        }
        if (a[k + 1] == b[i]) k++;
        if (k == n) {
            sol.push_back(i);
        }
    }
    int ap = sol.size();
    fout<<ap<<"\n";
    for (int i = 0; i < min(ap, 1000); i++) {
        fout<<sol[i] - n<<" ";
    }


    fin.close();
    fout.close();
    return 0;
}