Pagini recente » Borderou de evaluare (job #2677029) | Cod sursa (job #2827781) | Cod sursa (job #1276682) | Cod sursa (job #1421783) | Cod sursa (job #2910241)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
int nr, p[2000005], ans[1005], l, n, m; // l = len
int main() {
fin >> (a + 1);
fin >> (b + 1);
fin.close();
p[1] = 0;
n = strlen(a + 1), m = strlen(b + 1);
for(int i = 2; i <= n; i++) {
while(l != 0 && a[i] != a[l + 1]) {
l = p[l];
}
if(a[i] == a[l + 1]) {
l++;
}
p[i] = l;
}
l = 0;
for(int i = 1; i <= m; i++) {
while(l != 0 && b[i] != a[l + 1]) {
l = p[l];
}
if(b[i] == a[l + 1]) {
l++;
}
if(l == n) {
nr++;
if(nr <= 1000) {
ans[nr] = i - n;
}
l = p[l];
}
}
fout << nr << "\n";
for(int i = 1; i <= min(nr, 1000); i++) {
fout << ans[i] << " ";
}
return 0;
}