Pagini recente » Cod sursa (job #1282861) | Cod sursa (job #2981677) | Cod sursa (job #398560) | Cod sursa (job #1669955) | Cod sursa (job #672187)
Cod sursa(job #672187)
#include <fstream>
#include <string.h>
#define MIN(a, b) (a < b ? a : b)
int v[2000000],sol[1001];
char A[2000000],B[2000000];
int n,m;
void prefix(char* a)
{
int k = -1, x;
v[0] = 0;
for(x = 1; x < m; x++) {
while(k>0 && A[k+1]!=A[x])
k = v[k];
if(A[k+1] == A[x])
k++;
v[x] = k;
}
}
int main()
{
int i, x = -1, contor = 0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(A, 2000000);
f.getline(B, 2000000);
n = strlen(A);
m = strlen(B);
prefix(B);
for(i = 0; i < m; i++) {
while(x > 0 && A[x+1] != B[i])
x = v[x];
if(A[x+1] == B[i])
x++;
if(x == n-1) {
x=v[x];
if(contor <= 1000)
sol[contor] = i - (n-1);
++contor;
}
}
g<<contor<<"\n";
for(i=0;i<MIN(contor, 1000); i++) {
g<<sol[i]<<" ";
}
}