Pagini recente » Cod sursa (job #2017827) | Cod sursa (job #2132856) | Cod sursa (job #2522490) | Cod sursa (job #1245403) | Cod sursa (job #1795893)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000009
using namespace std;
char a[NMAX], b[NMAX], pi[NMAX];
int m, n;
vector <int> sol;
int main ()
{
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
cin >> (a + 1) >> (b + 1);
n = strlen (a + 1);
m = strlen (b + 1);
//cout << n << m;
pi[1] = 0;
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;
int ss = 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 && sol.size() < 1000)
sol.push_back (i - k);
if (k == n){
ss++;
k = pi[k];
}
}
cout << ss << "\n";
for (int i = 0; i < sol.size(); i++)
cout << sol[i] << " " ;
return 0;
}