Cod sursa(job #1409601)

Utilizator ArhivaArhiva Infoarena Arhiva Data 30 martie 2015 16:48:57
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
///Z ALGORITHM
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000004;
char a[NMAX], b[NMAX];
int sol[1004], lg, n, m, Z[NMAX], dp[NMAX];
inline void Z_Algorithm()
{
    int imax = 0, j,i, ii;
    Z[1] = 0;
    for(i = 2;i<=n;++i)
    {
        if(i <= imax+Z[imax]-1)
            Z[i] = min(n-i+1,Z[i-imax+1]);
        for(j = Z[i],ii = i+Z[i];ii <= n && a[j+1] == a[ii];++ii,++j);
        Z[i] = j;
        if(i+Z[i] > imax+Z[imax])
            imax  = i;
    }
}
inline void Solve()
{
    int imax = 0, j,i, ii;
    for(i = 1;i+n-1 <= m;++i)
    {
        if(i <= imax+dp[imax]-1)
            dp[i] = Z[i-imax+1];
        for(j = dp[i],ii = i+dp[i];ii <= m && j < n  && a[j+1] == b[ii];++ii,++j);
        dp[i] = j;
        if(j == n)
        {
            ++lg;
            if(lg <= 1000)
                sol[lg] = i-1;
        }
        if(i+dp[i] > imax+dp[imax])
            imax  = i;
    }

}
inline void Write()
{
    printf("%d\n",lg);
    lg = min(lg,1000);
    for(int i=1;i<=lg;++i)
        printf("%d ",sol[i]);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",(a+1),(b+1));
    n = strlen(a+1), m = strlen(b+1);
    Z_Algorithm();
    Solve();
    Write();
    return 0;
}