Cod sursa(job #2030003)

Utilizator mihai.alphamihai craciun mihai.alpha Data 30 septembrie 2017 20:31:31
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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);
    cin >> a + 1 >> b + 1;
    int n = strlen(a + 1), m = strlen(b + 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;
}