Pagini recente » Cod sursa (job #1431944) | Cod sursa (job #2682530) | Cod sursa (job #62858) | Cod sursa (job #1430177) | Cod sursa (job #2528870)
#include <fstream>
#define MAX 2000010
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int prsuf[MAX], indici[1005], k;
char a[MAX], b[MAX];
void kmp (){
int i, j;
j = 0;
for (i = 0; b[i]; i++) {
while (j > 0 && a[j] != b[i])
j = prsuf[j-1];
if (a[j] == b[i] )
j++;
if (!a[j]) {
k++;
if (k <= 1001)
indici[k] = i-j+1;
}
}
}
void prefix() {
int i = 0, j;
for (j = 1; a[j]; j++) {
while (i > 0 && a[i] != a[j])
i = prsuf[i-1];
if (a[i] == a[j]) {
i++;
prsuf[j] = prsuf[j-1]+1;
}
}
}
int main()
{
fin.getline(a, 2000005);
fin.getline(b, 2000005);
prefix();
kmp();
fout << k << "\n";
for (int i = 1; i <= 1000 && indici[i]; i++)
fout << indici[i] << " ";
return 0;
}