Pagini recente » Profil Voszy | Atasamentele paginii Clasament gagaga | Cod sursa (job #134840) | Cod sursa (job #1274024) | Cod sursa (job #1965098)
# 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;
}