Pagini recente » Cod sursa (job #1046130) | Diferente pentru utilizator/raresegay intre reviziile 14 si 13 | Cod sursa (job #2496299) | Cod sursa (job #47748) | Cod sursa (job #3195736)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
int table[2000005];
vector < int > res; // primii 1000 de indici ca solutii
int ans;
int n,m;
int i,k;
int main() {
fin>>a>>b;
n = strlen(a);
m = strlen(b);
table[0] = 0;
k = 0;
i = 1;
while(i<n) {
if (a[i] == a[k]) {
k++;
table[i] = k;
i++;
} else if (k!=0) {
k = table[k-1];
} else {
table[i] = 0;
i++;
}
}
i = 0,k = 0;
while(i<m) {
if (b[i] == a[k]) {
i++;
k++;
if (k==n) {
ans++;
if (ans<=1000) res.push_back(i-n);
k = table[k-1];
}
} else if (b[i] != a[k]) {
if (k!=0)
k = table[k-1];
else
i++;
}
}
fout<<ans<<endl;
for (auto el : res) {
fout<<el<<" ";
}
return 0;
}