Pagini recente » Cod sursa (job #473931) | Cod sursa (job #2247979) | Cod sursa (job #607037) | Cod sursa (job #328040) | Cod sursa (job #2361949)
#include <bits/stdc++.h>
#define p 67
using namespace std;
const int m = 1e9+9 ;
ifstream fin ("strmatch.in") ;
ofstream fout("strmatch.out") ;
string sir1 , sir2 ;
vector<int> sol;
int main()
{
int i ,sa,sb;
long long curh , hs=0 ;
fin >> sir1 ;
fin >> sir2 ;
if ( sir1.size() > sir2.size() )
{
fout << "0" ;
return 0 ;
}
vector<int> pp(sir2.size()+2) ;
pp[0] = 1 ;
for ( i = 1 ; i <= sir2.size()-1 ; i++ )
pp[i] = ( pp[i-1] * p ) % m ;
for ( i = 0 ; i <= sir1.size()-1 ; i++ )
{
if ( sir1[i] <= 'Z' && sir1[i] >= 'A' )
hs = ( hs + (sir1[i]-'A'+1) * pp[i] ) % m ;
else if ( sir1[i] <= 'z' && sir1[i] >= 'a' )
hs = ( hs + (sir1[i]-'a'+27) * pp[i] ) % m ;
else
hs = ( hs + (sir1[i]-'0'+53) * pp[i] ) % m ;
}
vector<long long> has(sir2.size()+2,0) ;
for ( i = 0 ; i <= sir2.size()-1 ; i++ )
{
if ( sir2[i] <= 'Z' && sir2[i] >='A' )
has[i+1] = ( has[i] + (sir2[i]-'A'+1) * pp[i] ) % m ;
else if ( sir2[i] <= 'z' && sir2[i] >= 'a' )
has[i+1] = ( has[i] + (sir2[i]-'a'+27) *pp[i] ) % m ;
else
has[i+1] = ( has[i] + (sir2[i]-'0'+53) *pp[i] ) % m ;
}
sa = sir1.size() ;
sb = sir2.size() ;
sir1.clear() ;
sir2.clear() ;
for ( i = 0 ; i + sa - 1 < sb ; i++ )
{
curh = ( has[i+sa] + m - has[i] ) % m ;
if ( curh == (1LL*hs * pp[i]) % m )
{
sol.push_back(i) ;
}
}
int ct = sol.size() ;
fout << ct << '\n' ;
for ( int ii = 0 ; ii < min(1000,ct) ; ii++ )
fout << sol[ii] << " " ;
}