Pagini recente » Cod sursa (job #2854059) | Cod sursa (job #1385225) | Cod sursa (job #2964958) | Cod sursa (job #741785) | Cod sursa (job #3275500)
#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 133
#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;
if(pattern.size() > text.size())
{
fout << 0;
return 0;
}
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 == t1 && p2 == t2) v[++n] = 0;
for(int i=pattern.size(); i<text.size(); ++i)
{
t1 = ((t1 - (text[i - pattern.size()] * h1) % mod1 + mod1) * b + text[i]) % mod1;
t2 = ((t2 - (text[i - pattern.size()] * h2) % mod2 + mod2) * b + text[i]) % mod2;
if(p1 == t1 && p2 == t2 && n < 1000) v[++n] = i - pattern.size() + 1;
else if(p1 == t1 && p2 == t2) ++n;
}
fout << n <<nn;
for(int i=1; i<=min(n,1000); ++i)
fout << v[i] <<" ";
}