Cod sursa(job #1563490)

Utilizator serbanSlincu Serban serban Data 6 ianuarie 2016 01:30:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

char a[2000005]; int n;
char b[2000005]; int m;
int pi[2000005], nr;
vector<int> ret;

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", &a); n = strlen(a);
    scanf("%s", &b); m = strlen(b);
    for(int i = n; i; i --) a[i] = a[i - 1];
    for(int i = m; i; i --) b[i] = b[i - 1];
    if(n > m) {cout << "0\n"; return 0;}

    int k = 0;
    for(int i = 2; i <= n; i ++) {
        while(k && a[i] != a[k + 1]) k = pi[k];
        if(a[i] == a[k + 1]) k ++;
        pi[i] = k;
    }

    k = 0;
    for(int i = 1; i <= m; i ++) {
        while(k && b[i] != a[k + 1]) k = pi[k];
        if(b[i] == a[k + 1]) k ++;
        if(k == n) {
            nr ++;
            ret.push_back(i - k);
            k = pi[n];
        }
    }

    cout << nr << "\n";
    for(int i = 0; i < ret.size() && i < 1000; i ++) cout << ret[i] << " ";
    cout << "\n";
    return 0;
}