Cod sursa(job #1536822)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 26 noiembrie 2015 18:22:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define MAXN 2000000
using namespace std;

string A, B;
vector <int> sol;
int pi[MAXN + 1];
int n, m;

void make_pi() {
    int q = 0;
    pi[1] = 0;

    for (int i = 2 ; i <= n ; ++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;
    A += 'w';
    B += 'w';
    n = A.size();
    m = B.size();

    for (int i = n - 1 ; i > 0 ; --i)
        A[i] = A[i - 1];
    for (int i = m - 1 ; i > 0 ; --i)
        B[i] = B[i - 1];

    --n;
    --m;
    make_pi();

    int q = 0;
    for (int i = 1 ; i <= m ; ++i) {
        while (q && A[q + 1] != B[i])
            q = pi[q];
        if (A[q + 1] == B[i])
            ++q;

        if (q == n) {
            q = pi[n];
            if (sol.size() < 1000)
                sol.push_back(i);
        }
    }

    cout << sol.size() << "\n";
    for (int i = 0 ; i < sol.size() ; ++i)
        cout << sol[i] - n << " ";
    cout << "\n";
    return 0;
}