Pagini recente » Cod sursa (job #1483262) | Cod sursa (job #454533) | Cod sursa (job #1497963) | Cod sursa (job #2823503) | Cod sursa (job #643246)
Cod sursa(job #643246)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define DN 2000013
#define DN2 10000000000000013LL
using namespace std;
char a[DN],b[DN];
long long q=1;
vector<int> v;
int main()
{
long long resta=0,restb=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w", stdout);
scanf("%s\n%s\n",a,b);
int n=strlen(a);
int m=strlen(b);
for(int i=0;i<n;i++)
{
resta=(resta*27+a[i]-'A'+1)%DN2;
q=(q*27)%DN2;
restb=(restb*27+b[i]-'A'+1)%DN2;
// cout<<resta<<" "<<restb<<" q:"<<q<<"\n";
}
if(resta==restb)
v.push_back(1);
for(int i=n;i<m;i++)
{
restb=(restb*27+b[i]-'A'+1)%DN2;
restb=(restb+DN2-(((b[i-n]-'A'+1)*q)%DN2))%DN2;
// cout<<restb<<endl;
if(restb==resta)
v.push_back(i-n+1);
}
printf("%d\n",v.size());
for(unsigned int i=0;i<v.size();i++) cout<<v[i]<<" ";
return 0;
}