Pagini recente » Cod sursa (job #1746061) | Cod sursa (job #857241) | Cod sursa (job #1224405) | Cod sursa (job #3146766) | Cod sursa (job #2616725)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
struct idk{
int fh,sh,poz;
};
idk v[NMAX];
char a[NMAX],b[NMAX];
int dp[25][NMAX],st,dr;
int rasp[NMAX];
int n,step,put,m;
bool cmp(idk a,idk b){
if(a.fh==b.fh) return a.sh<b.sh;
return a.fh<b.fh;
}
int lcp(int x,int y){
if(x==y) return n-x+1;
int rasp=0;
for(int i=step-1;i>=0;i--){
if(x>n or y>n) break;
if(dp[i][x]==dp[i][y]){
x+=(1<<i);
y+=(1<<i);
rasp+=(1<<i);
}
}
return rasp;
}
int main()
{
fin >> (b+1);
fin >> (a+1);
n=strlen(a+1);
int aux=n;
m=strlen(b+1);
a[n+1]='#';
for(int i=n+2;i<=n+m+1;i++){
a[i]=b[i-n-1];
}
n=n+m+1;
for(int i=1;i<=n;i++){
dp[0][i]=a[i]-'a';
}
step=0,put=1;
while(put/2<n){
step++;
for(int i=1;i<=n;i++){
v[i].fh=dp[step-1][i];
if(i+put>n) v[i].sh=-1;
else v[i].sh=dp[step-1][i+put];
v[i].poz=i;
}
sort(v+1,v+n+1,cmp);
dp[step][v[1].poz]=1;
int ind=1;
for(int i=2;i<=n;i++){
if(v[i].fh==v[i-1].fh and v[i].sh==v[i-1].sh)
dp[step][v[i].poz]=dp[step][v[i-1].poz];
else {
dp[step][v[i].poz]=++ind;
}
}
put*=2;
}
int rr=0;
int dim_rasp=0;
for(int i=1;i<=aux;i++){
int nr=lcp(i,aux+2);
if(nr==m){
rr++;
rasp[++dim_rasp]=i;
}
}
fout << rr << '\n';
for(int i=1;i<=dim_rasp;i++) fout << rasp[i]-1 << ' ';
return 0;
}