Pagini recente » Cod sursa (job #3305734) | Cod sursa (job #2204767) | Cod sursa (job #2204732) | Cod sursa (job #2204786) | Cod sursa (job #2403845)
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000000007
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char gs[2000002],s[2000002];
int n,m,i,j;
long long sum,tgsum;
long long nr;
bool ok;
vector <int> ans;
int main()
{
fin>>(gs+1);
fin>>(s+1);
m=strlen(gs+1);
n=strlen(s+1);
if(m>n)
{
fout<<0;
return 0;
}
for(i=1;i<=m;i++)
{
tgsum+=gs[i];
tgsum%=MOD;
}
for(i=1; i<=n-m+1; i++)
{
if(i==1)
for(j=1; j<=m; j++)
{
sum+=s[j];
sum%=MOD;
}
else
{
sum+=s[i+m-1];
sum-=s[i-1];
}
if(sum==tgsum)
{
ok=true;
for(j=i;j<=m+i-1;j++)
if(s[j]!=gs[j-i+1])
{
ok=false;
break;
}
if(ok==true)
nr++;
if(nr<=1000)
ans.push_back(i);
}
}
fout<<nr<<'\n';
for(auto par : ans)
fout<<par-1<<' ';
return 0;
}