Pagini recente » Cod sursa (job #1880269) | Cod sursa (job #1453262) | Cod sursa (job #2744975) | Cod sursa (job #1647976) | Cod sursa (job #2361834)
#include <bits/stdc++.h>
#define p 53
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()) ;
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' )
hs = ( hs + (sir1[i]-'A'+1) * pp[i] ) % m ;
else
hs = ( hs + (sir1[i]-'a'+27) * pp[i] ) % m ;
}
vector<long long> has(sir2.size(),0) ;
for ( i = 0 ; i <= sir2.size()-1 ; i++ )
{
if ( sir2[i] <= 'Z' )
has[i+1] = ( has[i] + (sir2[i]-'A'+1) * pp[i] ) % m ;
else
has[i+1] = ( has[i] + (sir2[i]-'a'+27)*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) ;
}
fout << sol.size() << '\n' ;
for ( auto ii : sol )
fout << ii << " " ;
}