Pagini recente » Cod sursa (job #388788) | Cod sursa (job #2689788) | Cod sursa (job #488912) | Cod sursa (job #671448) | Cod sursa (job #2684858)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out" );
vector <int> searchh ( string pat, string s )
{
int mod1 = 100007, mod2 = 100021, d = 256, h1 = 1, h2 = 1, p1 = 0, p2 = 0, t1 = 0, t2 = 0, i;
vector < int > sol;
int m = pat.size();
int n = s.size();
for ( i = 0 ; i < m-1 ; i++ )
{
h1 = (h1*d) % mod1;
h2 = (h2*d) % mod2;
}
for ( i = 0 ; i < m; i++ )
{
p1 = (p1 * d + pat[i]) % mod1;
p2 = (p2 * d + pat[i]) % mod2;
t1 = (t1 * d + s[i]) % mod1;
t2 = (t2 * d + s[i]) % mod2;
}
if ( p1 == t1 && p2 == t2 )
sol.push_back(0);
for ( i = m ; i < n ; i++ )
{
t1 = (d*(( t1 - h1*s[i-m])%mod1 + mod1 ) + s[i]) % mod1;
t2 = (d*(( t2 - h2*s[i-m])%mod2 + mod2 ) + s[i]) % mod2;
if ( t1 == p1 && t2 == p2 )
sol.push_back(i);
}
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 << " ";
}