Pagini recente » Cod sursa (job #1380058) | Cod sursa (job #2114167) | Cod sursa (job #819741) | Cod sursa (job #942224) | Cod sursa (job #3170197)
#include<fstream>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int i,j,pi[100005], potriviri[100005];
string s1,s2;
int main (void) {
in >> s1;
in >> s2;
pi[0] = -1;
j = -1;
for (int i = 0; i < s1.size(); i ++) {
while (j >= 0 && s1[i] != s1[j]) {
j = pi[j];
}
pi[i+1] = ++j;
}
int occ = 0;
j = 0;
for (int i = 0; i < s2.size(); i ++) {
while (j >= 0 && s2[i] != s1[j]) {
j = pi[j];
}
j ++;
if (j == s1.size()) {
occ ++;
if (occ <= 1000)
potriviri[occ] = i-s1.size()+1;
j = pi[j];
}
}
out << occ <<"\n";
for (int i = 1; i <= min(occ,1000); i ++) {
out << potriviri[i] <<" ";
}
return 0;
}