Pagini recente » Cod sursa (job #2903693) | Cod sursa (job #1693143) | Cod sursa (job #2039235) | Cod sursa (job #834315) | Cod sursa (job #2462283)
#include <bits/stdc++.h>
using namespace std;
char a[2000010], b[2000010];
int la, lb;
int v[2000010];
int numMatches, matches[1010];
void preprocess()
{
int k = -1;
v[0] = -1;
for(int i = 1; i < lb; i++)
{
while(k != -1 && b[i] != b[k + 1])
k = v[k];
if(b[i] == b[k + 1])
k++;
v[i] = k;
}
}
void match()
{
int k = -1;
for(int i = 0; i < la; i++)
{
while(k != -1 && a[i] != b[k + 1])
k = v[k];
if(a[i] == b[k + 1])
k++;
if(k == lb - 1)
{
if(numMatches < 1000)
matches[numMatches] = i - lb + 1;
numMatches++;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> b >> a;
la = strlen(a);
lb = strlen(b);
preprocess();
match();
cout << numMatches << '\n';
for(int i = 0; i < min(numMatches, 1000); i++)
cout << matches[i] << " ";
return 0;
}