Cod sursa(job #852363)

Utilizator SteveStefan Eniceicu Steve Data 11 ianuarie 2013 05:24:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string>
#include <vector>
 
using namespace std;
 
int N, M, T[2000011];
string A, B;
vector <int> v;
 
void Precalc ()
{
    int i = 0, pos = 2;
    T[0] = -1;
    T[1] = 0;
    while (pos < M)
    {
        if (B[pos - 1] == B[i]) T[pos++] = ++i;
        else if (i) i = T[i];
        else T[pos++] = 0;
    }
}
 
void KMP ()
{
    int m = 0, i = 0;
    while (m + i < N)
    {
        if (B[i] == A[m + i])
        {
            if (i == M - 2) v.push_back (m);
            i++;
        }
        else
        {
            m += i - T[i];
            i = max (T[i], 0);
        }
    }
}
 
int main ()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin >> B >> A;
    N = A.size ();
    B.push_back ('$');
    M = B.size ();
    fin.close ();
    Precalc ();
    KMP ();
    N = v.size ();
    fout << N << "\n";
    N = min (N, 1000);
    for (int i = 0; i < N; i++)
        fout << v[i] << " ";
    fout.close ();
    return 0;
}