Cod sursa(job #2238250)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 5 septembrie 2018 07:53:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;

#define NMAX 2000002

char a[NMAX], b[NMAX];
int pi[NMAX];

void prefix(char s[], int n) {
    int q = 0;
    pi[1] = 0;
    for (int i = 2; i <= n; i++) {
        while (q && s[i] != s[q + 1])
            q = pi[q];
        if (s[i] == s[q + 1])
            q++;
        pi[i] = q;
    }
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f >> (a + 1) >> (b + 1);
    int n = strlen(a + 1);
    int m = strlen(b + 1);

    prefix(a, n);

    vector <int> sol;
    int q = 0, cnt = 0;
    for (int i = 1; i <= m; i++) {
        while (q && b[i] != a[q + 1])
            q = pi[q];
        if (b[i] == a[q + 1])
            q++;
        if (q == n) {
            cnt++;
            if (cnt <= 1000)
                sol.push_back(i - n);
            q = pi[n];
        }
    }
    g << cnt << '\n';
    for (const auto& x:sol) {
        g << x << " ";
    }
    g.close();
    return 0;
}