Pagini recente » Cod sursa (job #367795) | Cod sursa (job #2594579) | Cod sursa (job #951947) | dsfdsf | Cod sursa (job #3136064)
#include<bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int P = 100003;
const int M = 1000000007;
string A,B;
int n,m,p=1,codA,codB,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];
codB=B[0];
for(int i=1;i<n;i++)
{
codA=(1LL*codA*P%M+A[i])%M;
p=1LL*p*P%M;
}
for(int i=1;i<n-1;i++)
codB=(1LL*codB*P%M+B[i])%M;
for(int st=0,dr=n-1;dr<m;st++,dr++)
{
codB=(1LL*codB*P%M+B[dr])%M;
if(codA==codB)
{
if(cnt<1000)
poz.push_back(st);
cnt++;
}
codB=(1LL*codB-1LL*p*B[st]%M+M)%M;
}
g<<cnt<<'\n';
for(auto it:poz)
g<<it<<' ';
return 0;
}