Pagini recente » Cod sursa (job #226288) | Cod sursa (job #2653368)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char s[4000005];
char s1[2000005];
int p[25][4000005];
int n,kk;
struct Pereche
{
int cur,nxt;
};
struct Aux
{
Pereche pereche;
int pozitie;
} v[4000005];
struct Sortare
{
int poz,ind;
} srt[4000005];
vector<int> sol;
bool cmp(const Aux &a, const Aux &b)
{
if(a.pereche.cur==b.pereche.cur){
if(a.pereche.nxt==b.pereche.nxt)
return a.pozitie<b.pozitie;
return a.pereche.nxt<b.pereche.nxt;
}
return a.pereche.cur<b.pereche.cur;
}
bool cmp2(const Sortare &a, const Sortare &b)
{
return a.poz<b.poz;
}
int lcp(int i,int j)
{
int l,i1,j1;
if(i==j)
return n-i;
l=0;
for(int put=kk; put>=0 && i<n && j<n; put--)
if(p[put][i]==p[put][j]){
i+=(1<<put);
j+=(1<<put);
l+=(1<<put);
}
return l;
}
int main()
{ freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int m,i,pw,j;
scanf("%s", s1);
scanf("%s", s);
n=strlen(s);
m=strlen(s1);
s[n]='#';
strcpy(s+n+1, s1);
n=n+m+1;
for(i=0; i<n; i++){
if(s[i]>='a' && s[i]<='z')
p[0][i]=s[i]-'a';
else{
if(s[i]>='A' && s[i]<='Z')
p[0][i]=s[i]-'A'+26;
else
p[0][i]=52;
}
}
for(kk=1,pw=1; pw/2<n; pw*=2,kk++){
for(i=0; i<n; i++){
v[i].pereche={p[kk-1][i], i+pw<n?p[kk-1][i+pw]:-1};
v[i].pozitie=i;
}
sort(v, v+n, cmp);
for(i=0; i<n; i++){
if(i>0 && v[i].pereche.cur==v[i-1].pereche.cur && v[i].pereche.nxt==v[i-1].pereche.nxt)
p[kk][v[i].pozitie]=p[kk][v[i-1].pozitie];
else
p[kk][v[i].pozitie]=i;
}
}
kk--;
for(i=0; i<n; i++){
srt[i].poz=p[kk][i];
srt[i].ind=i;
}
sort(srt, srt+n, cmp2);
for(i=0; i<n; i++)
if(srt[i].ind==n-m)
break;
for(j=i+1; j<n && sol.size()<1000; j++)
if(lcp(srt[i].ind, srt[j].ind)==m)
sol.push_back(srt[j].ind);
printf("%d\n", sol.size());
for(i=0; i<sol.size(); i++)
printf("%d ", sol[i]);
return 0;
}