Pagini recente » Cod sursa (job #1587132) | Cod sursa (job #160435) | Cod sursa (job #961795) | Cod sursa (job #819132) | Cod sursa (job #3219875)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string s,p;
int lps[1001];
vector<int> v;
int main()
{
fi>>p>>s;
lps[0] = 0;
int i = 1,k = 0;
while(i<p.size()) {
if (p[i]==p[k]) {
k++;
lps[i] = k;
i++;
} else {
if (k!=0) {
k = lps[k-1];
} else {
lps[i] = 0;
i++;
}
}
}
k = 0;
i = 0;
int rez = 0;
while(i<s.size()) {
if (s[i]==p[k]) {
i++;
k++;
if (k==p.size()) {
rez++;
v.push_back(i-k);
k = lps[k-1];
}
} else {
if (k!=0) {
k = lps[k-1];
} else {
i++;
}
}
}
fo<<rez<<'\n';
for (auto el : v)
fo<<el<<' ';
return 0;
}