Pagini recente » Cod sursa (job #1512900) | Cod sursa (job #2325792) | Cod sursa (job #222218) | Cod sursa (job #2323530) | Cod sursa (job #2842572)
#include <fstream>
#include <queue>
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=0,sum2=0,v1=0,v2=0,cnt=0,i;
cin>>s>>a;
for(i=0;i<s.size();i++)
{
sum1=0;
sum2=0;
sum1+=(s[i]-'A'+1);
sum2=sum1;
for(int j=i;j<s.size()-1;j++)
{
sum1*=27;
sum2*=27;
sum2%=666013;
sum1%=1000000007;
}
val1+=sum1;
val1%=1000000007;
val2+=sum2;
val2%=666013;
}
for(i=0;i<s.size();i++)
{
sum1=0;
sum2=0;
sum1+=(a[i]-'A'+1);
sum2=sum1;
for(int j=i;j<s.size()-1;j++)
{
sum1*=27;
sum2*=27;
sum2%=666013;
sum1%=1000000007;
}
v1+=sum1;
v1%=1000000007;
v2+=sum2;
v2%=666013;
}
if(v1==val1 && v2==val2)
{
q.push(0);
cnt++;
}
for(i;i<a.size();i++)
{
sum1=0;
sum2=0;
sum1+=(a[i-s.size()]-'A'+1);
sum2=sum1;
for(int j=0;j<s.size()-1;j++)
{
sum1*=27;
sum2*=27;
sum2%=666013;
sum1%=1000000007;
}
v1-=sum1;
v2-=sum2;
v1%=1000000007;
v2%=666013;
if(v1<0)
v1+=1000000007;
if(v2<0)
v2+=666013;
v1*=27;
v2*=27;
v1+=a[i]-'A'+1;
v2+=a[i]-'A'+1;
v1%=1000000007;
v2%=666013;
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;
}