Cod sursa(job #1420731)

Utilizator george_stelianChichirim George george_stelian Data 18 aprilie 2015 21:29:44
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int sigma=62;
char v[2000010],v1[2000010];
int pi[2000010],delta[100010][63],sol[1010];

int code(char c)
{
    if('0'<=c && c<='9') return c-'0';
    else if('A'<=c && c<='Z') return 10+c-'A';
    else return 36+c-'a';
}

char decode(int x)
{
    if(x<=9) return '0'+x;
    else if(x<=35) return 'A'+x-10;
    else return 'a'+x-36;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s",v+1,v1+1);
    int n=strlen(v+1),m=strlen(v1+1),nr=0;
    for(int i=2,k=0;i<=n;i++)
    {
        while(k && v[k+1]!=v[i]) k=pi[k];
        if(v[k+1]==v[i]) k++;
        pi[i]=k;
    }
    for(int i=0;i<sigma;i++)
        if(v[1]==decode(i)) delta[0][i]=1;
        else delta[0][i]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<sigma;j++)
            if(v[i+1]==decode(j)) delta[i][j]=i+1;
            else delta[i][j]=delta[pi[i]][j];
    for(int i=1,x=0;i<=m;i++)
    {
        x=delta[x][code(v1[i])];
        if(x==n)
        {
            nr++;
            if(nr<=1000) sol[nr]=i-n;
        }
    }
    printf("%d\n",nr);
    int lim=min(nr,1000);
    for(int i=1;i<=lim;i++) printf("%d ",sol[i]);
    return 0;
}