Pagini recente » Cod sursa (job #933009) | Cod sursa (job #2464718) | Cod sursa (job #3176963) | Cod sursa (job #426318) | Cod sursa (job #2312921)
// By Stefan Radu
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define sz(x) (int)(x).size ()
typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int main () {
string a, b;
cin >> b >> a;
a = '#' + b + '#' + a;
vector < int > kmp (sz (a) + 1);
int ans = 0, k = 0;
for (int i = 2; i < sz (kmp); ++ i) {
while (k) {
if (a[i] == a[k + 1]) {
break;
}
k = kmp[k];
}
if (a[i] == a[k + 1]) {
kmp[i] = k + 1;
++ k;
}
if (kmp[i] == sz (b)) {
++ ans;
}
}
cout << ans << '\n';
ans = 0;
for (int i = 1; i < sz (kmp); ++ i) {
if (kmp[i] == sz (b)) {
++ ans;
cout << i - 2 * sz (b) - 1 << ' ';
}
if (ans == 1000) break;
}
}