Cod sursa(job #1482633)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 7 septembrie 2015 17:54:15
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000010],b[2000010];
int prefix[2000010],sol[2000010],n,m;
void solve_prefix(){
    int i=0,j;
    prefix[1]=0;
    for(j=2;j<=m;j++){
        while(i>0&&a[i+1]!=a[j])
            i=prefix[i];
        if(a[i+1]==a[j])
            i++;
        prefix[j]=i;
    }
}
int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i,j,k;
    scanf("%s%s",&a,&b);
    m=strlen(a);
    n=strlen(b);
    for(i=n;i>=1;i--)
        a[i]=a[i-1];
    a[0]=NULL;
    for(i=m;i>=1;i--)
        b[i]=b[i-1];
    b[0]=NULL;
    solve_prefix();
    i=j=k=1;
    while(n-k>=m){
        while(j<=m&&b[i]==a[j]){
            i++;
            j++;
        }
        if(j>m){
            sol[0]++;
            sol[sol[0]]=k;
        }
        if(prefix[j-1]>0)
            k=i-prefix[j-1];
        else{
            if(i==k)
                i++;
            k=i;
        }
        if(j>1)
            j=prefix[j-1]+1;
    }
    printf("%d\n",sol[0]);
    for(i=1;i<=sol[0];i++)
        printf("%d ",sol[i]);
    return 0;
}