Cod sursa(job #1517006)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 3 noiembrie 2015 19:38:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<cstdio>
#include<cstring>
using namespace std;
char s[4000010];
int z[4000010],sol[1010];
int lit(char ch){
    if(ch>='a'&&ch<='z')
        return 1;
    if(ch>='A'&&ch<='Z')
        return 1;
    if(ch>='0'&&ch<='9')
        return 1;
    return 0;
}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int m,n,len,i,l=0,r=0,k,k0,r0,l0,lung,q,p,nr=0;
    scanf("%s",&s);
    p=strlen(s);
    scanf("%s",s+p);
    len=strlen(s);
    for(i=len;i>=1;i--)
        s[i]=s[i-1];
    s[0]=NULL;
    z[1]=l;
    for(k=2;k<=len;k++){
        if(k>r){
            lung=0;
            while(lit(s[k+lung])==1&&s[k+lung]==s[1+lung])
                lung++;
            z[k]=lung;
            l=k;
            r=k+lung-1;
        }
        else{
            if(k==1177)
                k0++;
            l0=1;
            r0=r-l+1;
            k0=k-l+1;
            if(z[k0]<r-k+1)
                z[k]=z[k0];
            else{
                lung=0;
                while(lit(s[r+lung])==1&&s[r+lung]==s[z[k0]+lung])
                    lung++;
                q=r+lung;
                z[k]=q-k;
                r=q-1;
                l=k;
            }
        }
        if(z[k]>=p&&k>p){
            nr++;
            if(nr<=1000)
                sol[nr]=k-p-1;
        }
    }
    printf("%d\n",nr);
    for(i=1;i<=nr&&i<=1000;i++)
        printf("%d ",sol[i]);
    return 0;
}