Pagini recente » Cod sursa (job #2470381) | Cod sursa (job #2281502) | Cod sursa (job #3265250) | Cod sursa (job #1185284) | Cod sursa (job #2462291)
#include <bits/stdc++.h>
using namespace std;
char str[4000020];
int lpattern, ltext, lstr;
int z[4000020];
int numMatches, matches[1010];
void reload(int i, int& l, int& r)
{
l = i;
r = max(r, i);
while(r < lstr && str[r - l] == str[r])
{
r++;
}
z[i] = r - l;
r--;
}
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;
}