Pagini recente » Cod sursa (job #2084861) | Cod sursa (job #171304) | Cod sursa (job #1843541) | Cod sursa (job #1892934) | Cod sursa (job #2723175)
#include <fstream>
#include <vector>
#include <string>
#define MOD1 1000000007
#define MOD2 1000000009
#define P 179
#define fi first
#define se second
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int finds, p1 = 1, p2 = 1, v[2000005];
vector <int> sol;
string pattern, s;
pair <long long, long long> genHash()
{
long long hash1 = 0, hash2 = 0;
for(auto it = pattern.begin(); it != pattern.end(); ++it)
{
hash1 = (((hash1 * P) % MOD1) + *it) % MOD1;
hash2 = (((hash2 * P) % MOD2) + *it) % MOD2;
if(it != pattern.begin())
{
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
}
return {hash1, hash2};
}
int main()
{
getline(cin, pattern);
getline(cin, s);
pair <long long, long long> ogh = genHash();
pair <long long, long long> amh;
int n = s.length();
int m = pattern.length();
for(auto i = 0; i < n; ++i)
{
if(i >= m)
{
amh.fi = 1ll * ((((amh.fi + MOD1 - (s[i - m] * p1) % MOD1) * P) % MOD1) + s[i]) % MOD1;
amh.se = 1ll * ((((amh.se + MOD2 - (s[i - m] * p2) % MOD2) * P) % MOD2) + s[i]) % MOD2;
}
else
{
amh.fi = 1ll * (((amh.fi * P) % MOD1) + s[i]) % MOD1;
amh.se = 1ll * (((amh.se * P) % MOD2) + s[i]) % MOD2;
}
if(amh == ogh)
{
++finds;
if(finds <= 1000)
sol.push_back(i - m + 1);
}
}
cout << finds << '\n';
for(auto it = sol.begin(); it != sol.end(); ++it)
cout << *it << ' ';
cout << '\n';
return 0;
}