Cod sursa(job #1379818)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 6 martie 2015 19:40:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

const int MAXN = 2000005;

string A, B;
int pi[MAXN], pos[1025];

void make_prefix(void) {
    int q = 0;
    pi[1] = 0;
    for(int i = 2; i < A.size(); ++i) {
        while(q && A[q + 1] != A[i])
            q = pi[q];
        if(A[q + 1] == A[i])
            ++q;
        pi[i] = q;
    }
}

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> A >> B;
    int q = 0, n = 0;
    A.insert(A.begin(), ' ');
    B.insert(B.begin(), ' ');

    make_prefix();

    for(int i = 1; i < B.size(); ++i) {
        while(q && A[q + 1] != B[i])
            q = pi[q];
        if(A[q + 1] == B[i])
            ++q;
        if (q == A.size() - 1) {
            q = pi[A.size() - 1];
            ++n;
            if(n <= 1000)
                pos[n] = i - A.size() + 1;
        }
    }

    cout << n << '\n';
    for(int i = 1; i <= min(n, 1000); ++i)
        cout << pos[i] << ' ';
    return 0;
}