Pagini recente » Cod sursa (job #84867) | Cod sursa (job #2250046) | Cod sursa (job #2108531) | Cod sursa (job #610009) | Cod sursa (job #2738882)
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
const int MOD3 = 1e9+13;
const int NMAX = 1e6*2;
char s1[NMAX+6] , s2[NMAX + 6];
vector<int>sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1,NMAX*2+5,stdin);
fgets(s2,NMAX*2+5,stdin);
int n = strlen(s1) , m = strlen(s2) , i;
--n ;
--m;
long long cnt1 = 0 , cnt2 = 0 , cnt3 = 0 ;
for(i = 0 ; i < n ;i++)
{
cnt1 = cnt1*50 + s1[i]-'0';
cnt2 = cnt2*50 + s1[i]-'0';
cnt1%=MOD1;
cnt2%=MOD2;
}
long long c1 = 0 , c2 = 0 ,p1 = 1, p2 = 1;
for(i = 0 ; i < n; i++)
{
c1 = c1*50 + s2[i]-'0';
c2 = c2*50 + s2[i]-'0';
c1%=MOD1;
c2%=MOD2;
if(n - i - 1)
{p1= p1*50;
p1%=MOD1;
p2*=50;
p2%=MOD2;}
}
int answer = 0 ;
if(c1 == cnt1 && c2 == cnt2)answer ++,sol.push_back(n-1);
for(i = n ; i < m; i++)
{
c1 -= p1*(s2[i-n]-'0');
c1 *= 50;
c1 += s2[i]-'0';
c1%=MOD1;
if(c1<0)c1+=MOD1;
c2 -= p2*(s2[i-n]-'0');
c2 *= 50;
c2 += s2[i]-'0';
c2%=MOD2;
if(c2<0)c2+=MOD2;
if(c1 == cnt1 && c2 == cnt2)answer ++,sol.push_back(i);
}
cout << answer<<endl;
for(auto edge : sol)
cout<<edge - n+1<< " ";
return 0;
}