Pagini recente » Cod sursa (job #2219604) | Cod sursa (job #1699479) | Cod sursa (job #1853761) | Cod sursa (job #2635240) | Cod sursa (job #715378)
Cod sursa(job #715378)
#include<cstdio>
#include<cstring>
#include<vector>
#define MOD 666013
#define MOD1 100279
using namespace std;
vector<int> V;
void read(),solve();
int SAB1,SAB2,PRE1[100010],PRE2[100010],SOL1,SOL2,i,K,PRE3[100010],PRE4[100010],SAB3,SAB4,SOL3,SOL4;
char A[100010],B[100010],*p;
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf(" %s",A);
scanf(" %s",B);
}
void solve()
{
PRE1[0]=PRE2[0]=1;
PRE3[0]=PRE4[0]=1;
K=strlen(A);
for(i=1;i<K;i++)
{
PRE1[i]=PRE1[i-1]*27;
PRE1[i]%=MOD;
PRE2[i]=PRE2[i-1]*29;
PRE2[i]%=MOD;
PRE3[i]=PRE3[i-1]*27;
PRE3[i]%=MOD1;
PRE4[i]=PRE4[i-1]*29;
PRE4[i]%=MOD1;
}
for(p=A,--i;*p;p++,i--)
{
SAB1+=(*p-'0'+1)*PRE1[i];
SAB1%=MOD;
SAB2+=(*p-'0'+1)*PRE2[i];
SAB2%=MOD;
SAB3+=(*p-'0'+1)*PRE3[i];
SAB3%=MOD1;
SAB4+=(*p-'0'+1)*PRE4[i];
SAB4%=MOD1;
}
for(p=B;*p;p++)
{
if(p-B<K)
{
SOL1+=(*p-'0'+1)*PRE1[K-(p-B)-1];
SOL1%=MOD;
SOL2+=(*p-'0'+1)*PRE2[K-(p-B)-1];
SOL2%=MOD;
SOL3+=(*p-'0'+1)*PRE3[K-(p-B)-1];
SOL3%=MOD1;
SOL4+=(*p-'0'+1)*PRE4[K-(p-B)-1];
SOL4%=MOD1;
continue;
}
if(SOL1==SAB1&&SOL2==SAB2&&SAB3==SOL3&&SAB4==SOL4)
{
V.push_back((p-B)-K);
if(V.size()==1000)break;
}
SOL1-=(*(p-K)-'0'+1)*PRE1[K-1];
while(SOL1<0)SOL1+=MOD;
SOL2-=(*(p-K)-'0'+1)*PRE2[K-1];
while(SOL2<0)SOL2+=MOD;
SOL3-=(*(p-K)-'0'+1)*PRE3[K-1];
while(SOL3<0)SOL3+=MOD1;
SOL4-=(*(p-K)-'0'+1)*PRE4[K-1];
while(SOL4<0)SOL4+=MOD1;
SOL1*=27;SOL2*=29;
SOL1%=MOD;SOL2%=MOD;
SOL1+=(*p-'0'+1);
SOL2+=(*p-'0'+1);
SOL3*=27;SOL4*=29;
SOL3%=MOD1;SOL4%=MOD1;
SOL3+=(*p-'0'+1);
SOL4+=(*p-'0'+1);
}
printf("%d\n",V.size());
for(vector<int>::iterator it=V.begin();it!=V.end();it++)printf("%d ",*it);
}