Pagini recente » Cod sursa (job #1781888) | Cod sursa (job #487564) | Cod sursa (job #2904433) | Cod sursa (job #1133714) | Cod sursa (job #2361887)
#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 ;
long long curh , hs=0 ;
fin >> sir1 ;
fin >> sir2 ;
if ( sir1.size() > sir2.size() )
{
fout << "0" ;
return 0 ;
}
vector<long long> pp(sir2.size()+1) ;
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) ;
if ( sir2[0] <= 'Z' && sir2[0] >='A' )
has[0] = (sir2[0]-'A'+1);
else if ( sir2[0] <= 'z' && sir2[0] >= 'a' )
has[0]= (sir2[0]-'a'+27);
else
has[0] = (sir2[0]-'0'+53) ;
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 ;
}
for ( i = 0 ; i + sir1.size() - 1 < sir2.size() ; i++ )
{
curh = ( has[i+sir1.size()] + m - has[i] ) % m ;
if ( curh == hs * pp[i] % m )
{
sol.push_back(i) ;
if ( sol.size() >= 1000 )
break ;
}
}
int ct = sol.size() ;
fout << min(1000,ct) << '\n' ;
for ( int ii = 0 ; ii < min(1000,ct) ; ii++ )
fout << sol[ii] << " " ;
}