Pagini recente » Cod sursa (job #1327850) | Cod sursa (job #572173) | Cod sursa (job #241042) | Cod sursa (job #400466) | Cod sursa (job #2338783)
#include <fstream>
#include <cstring>
using namespace std;
char a[2000010], b[2000010];
int p[2000010];
int n, m, L, sol;
int s[1010];
int main () {
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
fin>>a+1;
fin>>b+1;
n = strlen(a+1);
m = strlen(b+1);
p[1] = 0;
L = 0;
for (int i=2;i<=n;i++) {
while(L && 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 && b[i] != a[L+1])
L = p[L];
if (b[i] == a[L+1])
L++;
if (L == n) {
sol++;
if (sol <= 1000)
s[sol] = i-n;
L = p[L];
}
}
fout<<sol<<"\n";
for (int i=1;i<=min(sol, 1000);i++)
fout<<s[i]<<" ";
return 0;
}