Cod sursa(job #3238938)

Utilizator Allie28Radu Alesia Allie28 Data 31 iulie 2024 16:39:34
Problema Potrivirea sirurilor Scor 36
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 - 1

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

int main() {
    fin>>a>>b;
    n = strlen(a);
    m = strlen(b);
    Pi();
    int k = - 1;
    vector<int> sol;
    for (int i = 1; i < m; i++) {
        while (k  != -1 && a[k + 1] != b[i]) {
            k = pi[k];
        }
        if (a[k + 1] == b[i]) k++;
        if (k + 1 == 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 + 1<<" ";
    }


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