Pagini recente » Cod sursa (job #1432285) | Cod sursa (job #829401) | Cod sursa (job #2442415) | Cod sursa (job #501239) | Cod sursa (job #3214713)
///kmp deduction
///lps longest prefix == sufix
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int N = 4e6 + 10;
int pi[N + 1];
int n, st, dr, nr;
vector <int> v;
string path, s;
void kmp ()
{
for (int i = 1; i < s.size(); ++i)
{
int val = pi[i - 1];
while (val > 0 && s[val] != s[i])
val = pi[val - 1];
if (s[val] == s[i])
++val;
pi[i] = val;
if (pi[i] == n && i > n)
++nr, v.push_back(i - n * 2);
}
}
int main()
{
cin >> path >> s;
n = path.size();
s = path + '@' + s;
kmp ();
cout << nr << '\n';
for (int i = 0; i < min (1000, (int)v.size()); ++i)
cout << v[i] << ' ';
return 0;
}