Cod sursa(job #1250548)

Utilizator cojocarugabiReality cojocarugabi Data 28 octombrie 2014 12:29:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int nmax = 2e6 + 5;
const int amax = 1e3 + 5;
char A[nmax],B[nmax];
int p[nmax],s[amax];
int a,b;
int main(void)
{
    fi >> (A+1) >> (B+1);
    for (a=1;A[a];++a);--a;
    for (b=1;B[b];++b);--b;
    p[1]=0;
    for (int i=2,k=0;i<=a;++i)
    {
        while (k && A[k+1] != A[i]) k=p[k];
        k+=(A[k+1] == A[i]);p[i]=k;
    }
    for (int i=1,k=0;i<=b;++i)
    {
        while (k && A[k+1] != B[i]) k=p[k];
        k+=(A[k+1] == B[i]);
        if (k == a)
        {
            ++s[0];if (s[0] <= 1000) s[s[0]]=i-k;
            k=p[k];
        }
    }
    fo << s[0] << '\n';
    s[0]=min(s[0],1000);
    for (int i=1;i<=s[0];++i) fo << s[i] << ' ';
    return 0;
}