Pagini recente » Cod sursa (job #2809445) | Cod sursa (job #903174) | Cod sursa (job #539710) | Cod sursa (job #2047575) | Cod sursa (job #2713204)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
#define N 2000005
#define mod 1000003
int p, t;
int n, m, k;
char txt[N], pat[N];
int sol[N];
char Val (char s)
{
if (s >= 'a' && s <= 'z')
return s - 'a' + 1;
return s - 'A' + 1;
}
int main()
{
f >> pat >> txt;
n = strlen(txt); m = strlen(pat);
for (int i=0; i<m; i++)
{
p = (1LL * p + Val(pat[i])) % mod;
t = (1LL * t + Val(txt[i])) % mod;
}
for (int i=0; i<=n-m; i++)
{
if (p == t)
{
int cnt = 0;
for (int j=0; j<m; j++)
{
if (pat[j] != txt[i+j]) break;
cnt ++;
}
if (cnt == m && k < 1000) {
k ++; sol[k] = i;
}
}
if (i < n - m)
{
t = (1LL * t - Val(txt[i])) % mod;
t = (1LL * t + Val(txt[i+m])) % mod;
}
}
g << k << "\n";
for (int i=1; i<=k; i++)
g << sol[i] << " ";
return 0;
}