Cod sursa(job #1696618)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 29 aprilie 2016 15:40:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
void lol(){
    int x=0;
    x++;
}
using namespace std;
const int L=2000000;
char s1[L+1];
char s2[2*L+1];
int z[2*L+1];
int ans[L+1];
int l,r,n1,n2,res;
void set_z(){
    for(int i=1;i<n2+n1;i++){
        if(i==4)
            lol();
        if(r<i){
            int j=0;
            while(s2[j]==s2[i+j]&&j<n1)
                j++;
            j--;
            if(j>=0){
                r=j+i;
                l=i;
                z[i]=r-l+1;
            }
        }
        else{
            int ii=z[l]-(r-i+1);
            if(z[ii]){
                if(ii+z[ii]-1<z[l]-1){
                    z[i]=z[ii];
                    l=i;
                    r=i+z[i]-1;
                }
                else{
                    int j=r-i+1;
                    while(s2[j]==s2[i+j]&&j<n1)
                        j++;
                    j--;
                    r=j+i;
                    l=i;
                    z[i]=r-l+1;
                }
            }
        }
    }
}
void z_algo(){

}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(s2);
    gets(s1);
    n1=strlen(s1);
    n2=strlen(s2);
    for(int i=0;i<n1;i++)
        s2[n2+i]=s1[i];
    set_z();
    for(int i=n2;i<n2+n1;i++)
        if(z[i]>=n2)
            ans[++res]=i-n2;
    printf("%d\n",res);
    for(int i=1;i<=min(res,1000);i++)
        printf("%d ",ans[i]);
    return 0;
}