Pagini recente » Cod sursa (job #674907) | Cod sursa (job #2071200) | Cod sursa (job #519816) | Cod sursa (job #1165169) | Cod sursa (job #2861450)
#include <bits/stdc++.h>
using namespace std;
ifstream ci("strmatch.in");
ofstream cou("strmatch.out");
#define d 256
vector <int> v;
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++)
{
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++)
{
bool flag = true;
if ( p == t )
{
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
{
flag = false;
break;
}
}
if(flag)
v.push_back(i);
}
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;
if (t < 0)
t = (t + q);
}
}
}
char pat[2000001],txt[2000001];
int main()
{
ci>>pat;
ci>>txt;
int q = 101;
search(pat, txt, q);
cou<<v.size()<<'\n';
for (auto i : v)
cou<<i<<" ";
return 0;
}