Cod sursa(job #2030008)

Utilizator mihai.alphamihai craciun mihai.alpha Data 30 septembrie 2017 20:39:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

#define MAXN (int)2e6

char a[MAXN + 1];
char b[MAXN + 1];

#define in "strmatch.in"
#define out "strmatch.out"

int pi[MAXN + 1];
int an[MAXN + 1];

int main()  {
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    fgets(a + 1, MAXN + 1, stdin);
    fgets(b + 1, MAXN + 1, stdin);
    int n = strlen(a + 1) - 1, m = strlen(b + 1) - 1;
    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;
    int ans = 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)  {
            ans++;
            an[ans] = i;
        }
    }
    int aa = min(ans, 1000);
    cout << ans << "\n";
    for(int i = 1;i <= aa;i++)
        cout << an[i] - n << " ";
    return 0;
}