Cod sursa(job #962904)

Utilizator morgeMihailescu Georgiana morge Data 15 iunie 2013 22:21:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
#define in "strmatch.in"
#define out "strmatch.out"
#define N 2000005
#define min(x,y) (x > y ? y : x)
char A[N+5], B[N+5];
int U[N+5], n, m;
vector <int> sol;
int main () 
{	ifstream fin (in);
    fin.getline (A+1, N);
    fin.getline (B+1, N);
    fin.close();
    m = strlen (A+1);
    n = strlen (B+1);
    int 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) {
            k = U[m];
            sol.push_back (i - m);
        }
    }
    ofstream fout (out);
    fout << sol.size() << "\n";
    for (unsigned i = 0; i < min (sol.size(), 1000); ++i)
        fout << sol[i] << " ";
    fout << "\n";
    fout.close();
    return 0;
}