Cod sursa(job #1114180)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 21 februarie 2014 12:59:09
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define nmax 2000005
using namespace std;

vector <int> r;
int n,m,q,nr;
int has[nmax];
char a[nmax];
char b[nmax];

int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",a+1,b+1);
    n = strlen(a+1);
    m = strlen(b+1);
    for (int i=2;i <= n;i++) {
        while(q != 0 && a[i] != a[q+1]) q = has[q];
        if(a[i] == a[q+1]) q++;
        has[i] = q;
    }
    q = 0;
    for(int i=1;i <= m;i++) {
        while (q != 0 && b[i]!=a[q+1]) q = has[q];
        if (b[i] == a[q+1]) q++;
        nr++;
        if (q == n) if (r.size() < 1000) r.insert(r.begin(),i-n);
    }
    printf("%d\n",nr);
    while (!r.empty()) {
    	printf("%d ",r.back());
    	r.pop_back();
    }
    return 0;
}