Pagini recente » Cod sursa (job #502606) | Profil M@2Te4i | Diferente pentru implica-te/extinde-arhiva/autor-necunoscut intre reviziile 1 si 11 | Profil farte_vlad | Cod sursa (job #1474948)
//#include <stdio.h>
//#include <string.h>
//
//char a[2000005], b[2000005];
//int occ[1005], f[2000005], nOcc = 0, i, j, sizeP, sizeS;
//
//void buildF()
//{
// f[0] = -1;
// for (i = 1; i < sizeP; ++i)
// {
// j = f[i - 1];
// while (j != -1 && a[i - 1] != a[j])
// {
// j = f[j];
// }
// f[i] = j + 1;
// }
//}
//
//int main()
//{
// //freopen("strmatch.in", "r", stdin);
// //freopen("strmatch.out", "w", stdout);
//
// memset(a, 0, 2000005);
// memset(b, 0, 2000005);
//
// scanf("%s%s", a, b);
//
// sizeP = strlen(a);
// sizeS = strlen(b);
//
// buildF();//build the bad suffix good prefix function
//
// i = j = 0;
// while (i < sizeS)
// {
// if (b[i] == a[j])//the characters match
// {
// if (j == sizeP - 1)//found an occurence
// {
// occ[nOcc++] = i-j;
//
// if (nOcc == 1000)//max occurences found
// {
// break;
// }
//
// j = f[j];
// }
// else
// {
// i++;
// j++;
// }
// }
// else//use the bad suffix to find good prefix
// {
// if (j == 0)//no good prefix can exist, moving to the next char in string
// {
// i++;
// }
// else
// {
// j = f[j];
// }
// }
// }
//
// printf("%d\n", nOcc);
// for (i = 0; i < nOcc; ++i)
// {
// printf("%d ", occ[i]);
// }
//}
#include <stdio.h>
#include <string.h>
#define MAX_LEN 2000000
#define MAX_POS 1000
int pos[MAX_POS];
char a[MAX_LEN + 2];
char b[MAX_LEN + 2];
int pi[MAX_LEN]; // pi[i] = lungimea celui mai lung prefix al S[1..i]
// care este si sufix al S[1..i]
void buildPrefix(char *s, int length) {
int q = 0;
pi[0] = 0;
for (int i = 1; i < length; i++) {
while ((q > 0) && (s[i] != s[q])) {
q = pi[q - 1];
}
if (s[q] == s[i]) {
q++;
}
pi[i] = q;
}
}
int main(void) {
int n, m;
int q;
int ans;
FILE *f = fopen("strmatch.in", "r");
fgets(a, MAX_LEN + 2, f);
fgets(b, MAX_LEN + 2, f);
fclose(f);
n = strlen(a) - 1;
m = strlen(b) - 1;
buildPrefix(a, n);
q = 0;
ans = 0;
for (int i = 0; i < m; i++) {
while ((q > 0) && (a[q] != b[i])) {
q = pi[q - 1];
}
if (a[q] == b[i]) {
q++;
}
if (q == n) {
if (ans < MAX_POS) {
pos[ans] = i;
}
ans++;
}
}
f = fopen("strmatch.out", "w");
fprintf(f, "%d\n", ans);
if (ans > MAX_POS) {
ans = MAX_POS;
}
for (int i = 0; i < ans; i++) {
fprintf(f, "%d ", pos[i] - n + 1);
}
fclose(f);
return 0;
}