Cod sursa(job #638889)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 21 noiembrie 2011 20:20:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>
#define N 2000005
#define MMAX 1005
char A[N];
char B[N];
int pi[N];
int pos[MMAX];
int n, m;
using namespace std;

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

void Prefix() {
    int p = 0;
    pi[0] = 0;
    for(int i = 1; i < n; i++)  {
        while((A[p] != A[i]) && (p != 0))
            p = pi[p-1];
        if (A[p] == A[i])
         p++;
        pi[i] = p;
    }
}
void Solve() {
    int p = 0;
    int contor = 0;
    for(int i = 0; i < m; i++) {
        while((A[p] != B[i]) && (p != 0))
         p = pi[p-1];
        if(A[p] == B[i]) p++;
        if (p == n) {
            contor++;
            if (contor <= 1000)
             pos[contor] = i - n + 1;
            p = pi[p - 1];
        }
    }
    g << contor << "\n";
    for(int i = 1; i <= min(1000, contor); i++)
     g << pos[i]  << " ";
}
int main()
{
    f >> A >> B;
    n = strlen(A);
    m = strlen(B);
    Prefix();
    Solve();
    return 0;
}