Pagini recente » Cod sursa (job #1917266) | Cod sursa (job #1324651) | Cod sursa (job #2514279) | Cod sursa (job #1357860) | Cod sursa (job #3131450)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX = 2e6;
char a[NMAX + 1], b[NMAX + 1];
int lps[NMAX];
int positions[1001], ind = 0;
void LPS(char s[])
{
int n = strlen(s);
int i = 1, j = 0;
while (i < n)
{
if (s[i] == s[j])
{
j++;
lps[i] = j;
i++;
}
else
{
if (j > 0)
j = lps[j - 1];
else
{
lps[i] = 0;
i++;
}
}
}
}
int KMP(char a[], char b[])
{
LPS(b);
int n = strlen(a);
int m = strlen(b);
int i = 0, j = 0;
while ((n - i) >= (m - j))
{
if (a[i] == b[j])
{
i++;
j++;
}
if (j == m)
{
if(ind < 1000)
positions[ind++] = i - j;
j = lps[j - 1];
}
else if (i < n && a[i] != b[j])
{
if (j > 0)
j = lps[j - 1];
else
i++;
}
}
}
int main()
{
cin >> a >> b;
KMP(b, a);
cout << ind << '\n';
for(int i = 0; i < ind; i++)
cout << positions[i] << ' ';
return 0;
}