Pagini recente » Monitorul de evaluare | Cod sursa (job #2883503) | Cod sursa (job #1215037) | Cod sursa (job #239524) | Cod sursa (job #1248021)
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main(){
string W, S;
vector<int> T;
getline(in, W);
getline(in, S);
T.resize(W.length());
if (T.size()>1)
{ //kmp table
int pos = 2, cnd = 0;
T[0] = -1;
T[1] = 0;
while (pos < (int)W.length()){
if (W[pos - 1] == W[cnd]){
++cnd;
T[pos] = cnd;
++pos;
}
else if (cnd > 0){
cnd = T[cnd];
}
else{
T[pos] = 0;
++pos;
}
}
}
else{
T[0] = -1;
}
vector<int> matches;
int m = 0, i = 0;
while (m + i < (int)S.length()){
if (W[i] == S[m + i]){
if (i == (int)W.length() - 1){
matches.push_back(m);
if (T[i] > -1){
m = m + i - T[i];
i = T[i];
}
else{
i = 0;
++m;
}
continue;
}
++i;
}
else{
if (T[i] > -1){
m = m + i - T[i];
i = T[i];
}
else{
i = 0;
++m;
}
}
}
out << matches.size() << "\n";
for (i = 0; i < min((int)matches.size(), 1000); ++i){
out << matches[i] << " ";
}
return 0;
}