Pagini recente » Cod sursa (job #1410180) | Cod sursa (job #2296388) | Cod sursa (job #2849515) | Cod sursa (job #2816039) | Cod sursa (job #2705772)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int P = 2;
const int M = 1000000007;
const int P2 = 3;
const int M2 = 1000000003;
string A,B;
int n,m,p=1,p2=1,codA,codB,codA2,codB2,cnt;
vector<int> poz;
int main()
{
f>>A>>B;
n=A.size();
m=B.size();
if(n>m)
{
g<<"0\n";
return 0;
}
codA=A[0];
codA2=A[0];
codB=B[0];
codB2=B[0];
for(int i=1;i<n;i++)
{
codA=(1LL*codA*P%M+A[i])%M;
codA2=(1LL*codA2*P2%M2+A[i])%M2;
p=1LL*p*P%M;
p2=1LL*p2*P2%M2;
}
for(int i=1;i<n-1;i++)
{
codB=(1LL*codB*P%M+B[i])%M;
codB2=(1LL*codB2*P2%M2+B[i])%M2;
}
for(int st=0,dr=n-1;dr<m;st++,dr++)
{
codB=(1LL*codB*P%M+B[dr])%M;
codB2=(1LL*codB2*P2%M2+B[dr])%M2;
if(codB==codA&&codA2==codB2)
{
cnt++;
if(cnt<1000)
poz.push_back(st);
}
codB=(1LL*codB-1LL*p*B[st]%M+M)%M;
codB2=(1LL*codB2-1LL*p2*B[st]%M2+M2)%M2;
}
g<<cnt<<'\n';
for(auto it:poz)
g<<it<<' ';
return 0;
}