Cod sursa(job #1933890)

Utilizator serbanSlincu Serban serban Data 20 martie 2017 23:29:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> ret;

char a[2000005];
char b[2000005];
int prefix[2000005];

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

    f >> a;
    int n = strlen(a);
    for(int i = n + 1; i > 0; i --) a[i] = a[i - 1];

    f >> b;
    int m = strlen(b);
    for(int i = m + 1; i > 0; i --) b[i] = b[i - 1];

    if(n > m) {
        g << "0\n";
        return 0;
    }

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

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


    g << ret.size() << "\n";
    int lim = min(1000, (int)ret.size());
    for(int i = 0; i < lim; i ++) g << ret[i] << " ";
    g << "\n";
    return 0;
}