Cod sursa(job #1871427)

Utilizator SilviuIIon Silviu SilviuI Data 7 februarie 2017 13:06:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <vector>
#include <cstring>
#define nmax 2000010

using namespace std;

int n, m, k, nr;
int pred[nmax];
char s[nmax], ss[nmax];

vector <int> ans;

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

    gets(s + 1); n = strlen(s + 1);
    gets(ss + 1); m = strlen(ss + 1);

    pred[1] = 0; k = 0;

    for (int i = 2; i <= n; i++) {

        while (k > 0 && s[i] != s[k + 1]) k = pred[k];

        if (s[i] == s[k + 1]) k++;

        pred[i] = k;

    }

    k = 0;

    for (int i = 1; i <= m; i++) {

        while (k > 0 && ss[i] != s[k + 1]) k = pred[k];

        if (ss[i] == s[k + 1]) k++;

        if (k == n) {

            nr++;

            if (ans.size() < 1000) ans.push_back(i - n);

            k = pred[k];

        }
    }

    printf("%d\n", nr);

    for (int i = 0; i < (int)ans.size(); i++) printf("%d ", ans[i]);

    return 0;
}