Cod sursa(job #1399556)

Utilizator 4ONI2015oni2015 4ONI2015 Data 24 martie 2015 20:08:06
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
char s[2000005], t[2000005];
int p[2000005], n;
vector<int>sol;
void prefix()
{
    int k = 0, i;
    n = strlen(s + 1);
    for(i = 2; i <= n; i++)
    {
        while(k && s[k + 1] != s[i])k = p[k];
        if(s[i] == s[k + 1])
            k++;
        p[i] = k;
    }
}
void kmp()
{
    int k = 0, m = strlen(t + 1), i;
    for(i = 1; i <= m; i++)
    {
        while(k && s[k + 1] != t[i])k = p[k];
        if(t[i] == s[k + 1])
            k++;
        if(k == n)
            sol.pb(i - n);
    }
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", s + 1, t + 1);
    prefix();
    kmp();
    printf("%d\n", sol.size());
    int i = 0;
    for(auto it : sol)
    {
        printf("%d ", it);
        i++
        if (i == 1000)
            return 0;
    }
    return 0;
}