Pagini recente » Cod sursa (job #75021) | Cod sursa (job #2926876) | Cod sursa (job #173165) | Cod sursa (job #3225278) | Cod sursa (job #3246774)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int pq[2000005], nr;
vector<int> result;
void read() {
f>>a;
f>>b;
a.insert(0, " ");
b.insert(0, " ");
f.close();
}
void precompute() {
int q = 0;
for(int i = 2;i < a.size();++i) {
while(q && a[q + 1] != a[i]) {
q = pq[q];
}
if(a[q + 1] == a[i]) {
q++;
}
pq[i] = q;
}
}
void solve() {
int q = 0;
for(int i = 1;i < b.size();++i) {
while(q && a[q + 1] != b[i]) {
q = pq[q];
}
if(a[q + 1] == b[i]) {
q++;
}
if(q == a.size() - 1) {
nr++;
if(nr <= 1000) {
result.push_back(i - q);
}
q = pq[q];
}
}
}
void print() {
g<<nr<<'\n';
for(const auto& poz : result) {
g<<poz<<" ";
}
g.close();
}
int main() {
read();
precompute();
solve();
print();
return 0;
}