Pagini recente » Cod sursa (job #2718917) | Cod sursa (job #3242615) | Cod sursa (job #199001) | Cod sursa (job #1017896) | Cod sursa (job #643240)
Cod sursa(job #643240)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define DN 2000001
#define DN2 10000000
using namespace std;
char a[DN],b[DN];
long long q=1;
vector<int> v;
int main()
{
int resta=0,restb=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w", stdout);
scanf("%s\n%s",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+-(((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(int i=0;i<v.size();i++) cout<<v[i]<<" ";
return 0;
}