Pagini recente » Cod sursa (job #3285747) | Cod sursa (job #2046914) | Cod sursa (job #2097002) | Cod sursa (job #2076693) | Cod sursa (job #879643)
Cod sursa(job #879643)
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, s;
fin >> a >> s;
int maxmatch[a.length()];// store last index of longest substring that is both prefix and suffix
maxmatch[0]=-1;
for (size_t i=1; i<a.length(); ++i) {
int best=maxmatch[i-1];
while (true) {
if (a[best+1]==a[i]) {
++best;
break;
}
if (best==-1) break;
best=maxmatch[best];
}
maxmatch[i]=best;
}
//for (size_t i=0; i<a.length(); ++i) fout << maxmatch[i] << ' '; fout << '\n';
int best=-1;
vector<int> last;
for (size_t i=0; i<s.length(); ++i) {
while (true) {
if (a[best+1]==s[i]) {
++best;
if (best==int(a.length())-1) {
last.push_back(i);
best=maxmatch[best];
}
break;
}
if (best==-1) break;
best=maxmatch[best];
}
}
fout << last.size() << '\n';
int num=min(int(last.size()),1000);
for (int i=0; i<num; ++i)
fout << last[i]-a.length()+1 << ' ';
return 0;
}