Cod sursa(job #1165294)

Utilizator tudorv96Tudor Varan tudorv96 Data 2 aprilie 2014 16:46:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

#define min(x,y) ((x)<(y)?(x):(y))

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

const int N = 2e6 + 5;

int U[N], n;
char a[N], b[N];
vector <int> sol;

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