Cod sursa(job #1745976)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 22 august 2016 16:29:34
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

const int SMAX = 2000005;

char a[SMAX],
     b[SMAX];
int pi[SMAX];

vector<int> matches;

int main(void) {
    freopen("strmatch.in",  "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int t, l, ant;

    gets(a + 1);
    gets(b + 1);

    pi[1] = 0;
    ant   = 0;
    t     = 0;
    l     = 1;

    for(int i=2; a[i]; ++i) {
        ++l;
    }

    t = 0;
    for(int i=1; b[i]; ++i) {
        while(t && a[t+1]!=b[i])
            t = pi[t];
        if(a[t+1]==b[i])
            ++t;
        if(t==l) {
            t = pi[l];
            ++ant;
            if(ant<=1000)
                matches.push_back(i - l);
        }
    }

    printf("%d\n",ant);
    for(auto i:matches)
        printf("%d ",i);
    printf("\n");

    fclose(stdin);
    fclose(stdout);
    return 0;
}