Pagini recente » Cod sursa (job #2821808) | Cod sursa (job #68159) | Cod sursa (job #2856240) | Cod sursa (job #312663) | Cod sursa (job #2780855)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int const NMAX = 2000000;
string x, y;
int pre[1 + NMAX];
void buildPre() {
//we already know pre[0] = 0, so we go directly to pre[1]
int i = 0, j = 1;
while(j < x.size()) {
if(x[i] == x[j]) {
i++;
pre[j] = i;
j++;
} else {
if(i == 0) {
pre[j] = 0;
j++;
} else {
i = pre[i-1];
}
}
}
}
int main() {
fin >> x >> y;
buildPre();
vector<int> sol;
int ans = 0;
int i = 0, j = 0;
//i and j are the last matching letters in common prefix => x[0..i] matches y[j-L+1..j]
while(j < y.size()) {
if(x[i] == y[j]) {
i++;
j++;
}
if(i == x.size()) {
if(sol.size() < 1000) {
sol.push_back(j - x.size());
}
ans++;
i = pre[i-1];
} else if(i < x.size() && x[i] != y[j]) {
if(i == 0) {
j++;
} else {
i = pre[i-1];
}
}
}
fout << ans << "\n";
for(auto i : sol) {
fout << i << " ";
}
return 0;
}
/*while(j < y.size()) {
while(i < x.size() && x[i] == y[j]) {
i++;
j++;
}
if(i == 0) {
j++;
} else {
if(i == x.size()) {
if(sol.size() < 1000) {
sol.push_back(j - x.size());
}
ans++;
}
i = pre[i-1];
}
}*/