Pagini recente » Cod sursa (job #2702156) | Cod sursa (job #239297) | Cod sursa (job #2809157) | Cod sursa (job #3223753) | Cod sursa (job #3300551)
#include <fstream>
#include <cstring>
#define SMAX 2000005
#define ALFMAX 100
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 1e9 + 7;
char pattern[SMAX];
char s[SMAX];
int n, m;
int rez[SMAX]; int nr;
int k, i;
bool verif(int);
int main()
{
fin >> pattern >> s;
int m = strlen(pattern);
int n = strlen(s);
long long int x = 0, y = 0, p = 1;
for (i = 0; i < m; ++i)
{
x = x * ALFMAX % MOD + (pattern[i] - '0'); x %= MOD;
y = y * ALFMAX % MOD + (s[i] - '0'); y %= MOD;
if (i < m-1) p *= ALFMAX, p %= MOD;
}
if (y == x)
if (verif(0))
rez[++nr] = 0;
for (i = 1; i + m - 1 < n; i++)
{
y = ((y - p * (s[i - 1] - '0') % MOD + MOD) * ALFMAX + (s[i + m - 1] - '0')) % MOD;
if (y == x)
if (verif(i))
if (nr <= 1000) rez[++nr] = i;
else nr++;
}
fout << nr << '\n';
for (i = 1; i <= min(nr, 1000); ++i)
fout << rez[i] << ' ';
fout << '\n';
return 0;
}
bool verif(int pos)
{
for (int i = 0; i < m; ++i)
if (s[pos + i] != pattern[i])
return 0;
return 1;
}