Pagini recente » Cod sursa (job #2480262) | Cod sursa (job #1707968) | Cod sursa (job #1366006) | Cod sursa (job #1259798) | Cod sursa (job #2842618)
#include <fstream>
#include <queue>
#define hash1 1000000007
#define hash2 666013
using namespace std;
queue <int> q;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s,a;
long long int val1=0,val2=0,sum1=1,sum2=1,v1=0,v2=0,cnt=0,i;
cin>>s>>a;
for(i=0;i<s.size();i++)
{
val1=(val1*59+s[i])%hash1;
val2=(val2*59+s[i])%hash2;
v1=(v1*59+a[i])%hash1;
v2=(v2*59+a[i])%hash2;
if(i!=s.size()-1)
{
sum1*=59;
sum1%=hash1;
sum2*=59;
sum2%=hash2;
}
}
if(v1==val1 && v2==val2)
{
q.push(0);
cnt++;
}
for(i;i<a.size();i++)
{
v1-=a[i-s.size()]*sum1;
v2-=a[i-s.size()]*sum2;
v1%=hash1;
v2%=hash2;
if(v1<0)
v1+=hash1;
if(v2<0)
v2+=hash2;
v1*=59;
v2*=59;
v1+=a[i];
v2+=a[i];
v1%=hash1;
v2%=hash2;
if(v1==val1 && v2==val2)
{
cnt++;
if(q.size()<1000)
q.push(i-s.size()+1);
}
}
cout<<cnt<<'\n';
while(!q.empty())
{
cout<<q.front()<<" ";
q.pop();
}
return 0;
}