Pagini recente » Cod sursa (job #2158181) | Cod sursa (job #3217939) | Cod sursa (job #830009) | Cod sursa (job #591008) | Cod sursa (job #2462289)
#include <bits/stdc++.h>
using namespace std;
char str[4000020];
int lpattern, ltext, lstr;
int z[2000010];
int numMatches, matches[1010];
void reload(int i, int& l, int& r)
{
l = i;
r = max(r, i);
int c = 0;
while(r < lstr && str[c] == str[r])
{
r++;
c++;
}
r--;
z[i] = c;
}
void match()
{
int l = 0, r = 0;
for(int i = 1; i < lstr; i++)
{
if(i > r)
{
reload(i, l, r);
}
else
{
int k = i - l;
if(z[k] <= r - i)
z[i] = z[k];
else reload(i, l, r);
}
if(z[i] == lpattern)
{
if(numMatches < 1000)
matches[numMatches] = i - lpattern - 1;
numMatches++;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> str;
lpattern = strlen(str);
str[lpattern] = '$';
cin >> (str + lpattern + 1);
ltext = strlen(str + lpattern + 1);
lstr = lpattern + ltext + 1;
match();
cout << numMatches << '\n';
for(int i = 0; i < min(numMatches, 1000); i++)
cout << matches[i] << " ";
return 0;
}