Cod sursa(job #3195118)

Utilizator DARIUSQSDarius Nicoara DARIUSQS Data 20 ianuarie 2024 09:47:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[2000005], b[2000005];
int tabel[2000005];
vector < int > res; /// primii 1000 de indici ca solutii
int ans; /// numarul total de solutii
int n, m; /// n - dim lui a, m - dim lui b
/// tabel - tabelul din algoritmul kmp pentru sirul cautat (pentru sirul a)
int i, j, k;

int main()
{
    f >> a >> b;
    n = strlen(a); m = strlen(b);
    /// 1. construirea tabelului pentru sirul cautat
    /// tabel[0] = 0;
    i = 1;
    while (i<n) {
        if (a[i]==a[k]) {
            k++;
            tabel[i] = k;
            i++;
        }
        else if (k!=0) {
            k = tabel[k-1];
        }
        else {
            tabel[i] = 0;
            i++;
        }
    }

    /// 2. rezolvarea problemei
    k = 0;
    i = 0;
    while (i<m) {
        if (b[i]==a[k]) {
            i++;
            k++;
            if (k==n) {
                ans++;
                if (ans<=1000) {
                    res.push_back(i-n);
                }
                k = tabel[k-1];
            }
        }
        else if (b[i]!=a[k]) {
            if (k!=0) {
                k = tabel[k-1];
            }
            else i++;
        }
    }
    g << ans << '\n';
    for (auto x:res) {
        g << x << " ";
    }
    return 0;
}