Cod sursa(job #1965098)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 13 aprilie 2017 22:38:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
# include <fstream>
# include <cstring>
# define DIM 4000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char v[DIM];
int d[DIM],val[DIM],n,m,i,j,t,sol,st,dr;
int main () {
    fin>>v+1;
    n=strlen(v+1);
    fin>>v+n+1;
    m=strlen(v+1)-n;
    for(i=2;i<=n+m;i++){
        if(dr<i){
            for(t=1,j=i;v[t]==v[j]&&j<=n+m;t++,j++);
            if(j>i){
                st=i;
                dr=j-1;
                d[i]=t-1;
            }
            if(d[i]>=n&&i>n)
                val[++sol]=i-n-1;
            continue;
        }
        d[i]=min(d[i-st+1],dr-i+1);
        if(d[i-st+1]>dr-i){
            for(t=min(d[i-st+1],dr-i+1)+1,j=dr+1;v[t]==v[j]&&j<=n+m;t++,j++);
            if(j>dr){
                st=i;
                dr=j-1;
                d[i]=t-1;
            }
        }
        if(d[i]>=n&&i>n)
            val[++sol]=i-n-1;
    }
    fout<<sol<<"\n";
    for(i=1;i<=min(sol,1000);i++)
        fout<<val[i]<<" ";
    fout<<"\n";
    return 0;
}