Pagini recente » Cod sursa (job #1043313) | Cod sursa (job #78868) | Cod sursa (job #2900536) | Cod sursa (job #2934664) | Cod sursa (job #2684853)
#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, i , j;
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 ( i = 0 ; i <= s.size() - M; i++ )
{
if ( p == t )
{
for ( j = 0 ; j < M ; j++ )
{
if ( pat[j] != s[j+i] )
break;
}
if ( j == 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 << " ";
}