Cod sursa(job #1428118)

Utilizator stefanzzzStefan Popa stefanzzz Data 3 mai 2015 18:34:57
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAXA 4000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n, x = -1, kmp[MAXA];
string a, b;
vector<int> sol;

int main() {
    int i;

    f >> a >> b;
    
    n = a.length();
    a += b;

    kmp[0] = -1;
    for(i = 1; i < a.length() && sol.size() < 1000; i++) {
        while(x >= 0 && a[i] != a[x + 1]) x = kmp[x];
        if(a[i] == a[x + 1]) x++;
        kmp[i] = x;

        if(x >= n - 1 && i >= 2 * n - 1)
            sol.push_back(i - 2 * n + 1);
    }
        
    g << sol.size() << '\n';
    for(i = 0; i < sol.size(); i++)
        g << sol[i] << ' ';
    g << '\n';

    return 0;
}