Pagini recente » Cod sursa (job #462841) | Cod sursa (job #2154474) | Cod sursa (job #825004) | Cod sursa (job #1539011) | Cod sursa (job #2276424)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef int ull;
inline ull minim(ull a, ull b) {
return (a < b) ? a : b;
}
#define NMAX 2000005
void make_prefix(string A, vector<ull> & pi) {
int n = A.length();
for (int i=2, q=0; i <= n; ++i) {
for (; q != 0 && A[q] != A[i-1]; q = pi[q]);
if (A[i-1] == A[q]) q++;
pi[i] = q;
}
}
int main(void) {
int i, q = 0, n = 0;
ifstream iff("strmatch.in");
ofstream off("strmatch.out");
string A,B;
iff >> A >> B;
vector<ull> pos;
vector<ull> pi(A.length() + 1, 0);
make_prefix(A, pi);
for (i = 0, q=0; i < (int)B.length(); ++i) {
for (;q!=0 && A[q] != B[i-1]; q=pi[q]);
if (A[q] == B[i-1]) q++;
if (q == (int)A.length()) {
n++;
if (n <= 1000) {
pos.push_back(i - q);
}
}
}
off << n;
if (pos.size()) {
off << endl;
}
for (int i = 0; i < (int)pos.size(); ++i) {
off << pos[i] << " ";
}
off.close();
}