Pagini recente » Cod sursa (job #903119) | Cod sursa (job #1256981) | Cod sursa (job #2590229) | Cod sursa (job #1375954) | Cod sursa (job #3275475)
#include <bits/stdc++.h>
using namespace std;
#define nn "\n"
#define il inline
#define se second
#define fi first
#define pb push_back
#define pf push_front
#define in insert
#define int long long
#define b 135
#define mod1 100007
#define mod2 100021
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern,text;
int v[1003],n;
int h1 = 1, h2 = 1, p1,t1, p2,t2;
signed main()
{
fin >> pattern >> text;
for(int i=0; i<pattern.size(); ++i)
{
if(i != 0)
{
h1 = h1 * b % mod1;
h2 = h2 * b % mod2;
}
p1 = (p1 * b + pattern[i]) % mod1;
p2 = (p2 * b + pattern[i]) % mod2;
t1 = (t1 * b + text[i]) % mod1;
t2 = (t2 * b + text[i]) % mod2;
}
if(p1 == t2 && p1 == t1) v[++n] = 0;
for(int i=pattern.size(); i<=text.size(); ++i)
{
t1 = ((t1 - (h1 * text[i - pattern.size()]) % mod1 + mod1) % mod1 * b + text[i]) % mod1;
t2 = ((t2 - (h2 * text[i - pattern.size()]) % mod2 + mod2) % mod2 * b + text[i]) % mod2;
if(p1 == t1 && p2 == t2 && n < 1000) v[++n] = i - pattern.size() + 1;
}
fout << n <<nn;
for(int i=1; i<=n; ++i)
fout << v[i] <<" ";
}