Pagini recente » Istoria paginii utilizator/florin090503 | Cod sursa (job #2009262) | Cod sursa (job #2934645) | Clasament dupa rating | Cod sursa (job #1795940)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000040
using namespace std;
int pi[NMAX], sol[NMAX], s, n, m;
char a[NMAX], b[NMAX];
int main ()
{
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
cin >> a + 1 >> b + 1;
n = strlen (a + 1);
m = strlen (b + 1);
int k = 0;
for (int i = 2; i <= n; i++)
{
while (k && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
k++;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; i++)
{
while (k && a[k + 1] != b[i])
k = pi[k];
if (a[k + 1] == b[i])
k++;
if (k == n)
{
s++;
if (s <= 1000)
sol[s] = i - k;
k = pi[k];
}
}
cout << s << "\n" ;
for (int i = 1; i <= min (1000,s); i++)
cout << sol[i] << " ";
return 0;
}