Pagini recente » Cod sursa (job #36752) | Cod sursa (job #2107487) | Cod sursa (job #2185539) | Cod sursa (job #1804332) | Cod sursa (job #2684852)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out" );
vector <int> searchh ( string pat, string s )
{
int mod = 1000000007, d = 256, h = 1, p = 0, t = 0;
vector < int > sol;
int M = pat.size();
for ( int i = 0 ; i < M - 1 ; i++ )
h = (h*d) % mod;
for ( int i = 0 ; i < M ; i++ )
{
p = (d * p + pat[i]) % mod;
t = (d * t + s[i] ) % mod;
}
for ( int i = 0 ; i <= s.size() - M; i++ )
{
if ( p == t )
{
int j = i;
for ( j = i ; j < i + M ; j++ )
{
if ( pat[j-i] != s[j] )
break;
}
if ( j == i + M )
sol.push_back(i);
}
if ( i == s.size() - M )
break;
t = (d*( t - s[i]*h ) + s[i+M]) % mod;
if ( t < 0 )
t = t + mod;
}
return sol;
}
int main ()
{
string a, b;
vector <int> sol;
f >> a >> b;
sol = searchh ( a, b );
g << sol.size() << '\n';
for ( auto it : sol )
g << it << " ";
}