Pagini recente » Cod sursa (job #881686) | Cod sursa (job #440335) | Cod sursa (job #2594033) | Cod sursa (job #412578) | Cod sursa (job #1073920)
#include<stdio.h>
#include<string.h>
#define NMAX 2000000
char text[NMAX], pat[NMAX];
int func[NMAX];
void failureFunction() {
int lung = strlen(pat);
int j = 0;
func[0] = 0;
for(int i = 1; i < lung; ++i) {
if(pat[i] == pat[j]) {
j++;
} else {
j = (pat[i] == pat[0]) ? 1 : 0;
}
func[i] = j;
}
}
int gasit[NMAX], gasitLen = 0;
void kmp() {
int patLen = strlen(pat), textLen = strlen(text);
for(int i = 0, j = 0; i < textLen; i++) {
if(text[i] == pat[j]) {
j++;
} else {
j = j > 1? func[j - 1] : 0;
if(text[i] == pat[j]) {
j++;
}
}
if(j == patLen) {
// printf("Gasit: %d\n", i - j + 1);
gasit[gasitLen++] = i - j + 1;
i -= func[j-1];
j = func[j-1];
}
}
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",pat);
scanf("%s",text);
failureFunction();
kmp();
// afisare
printf("%d\n", gasitLen);
for ( int i = 0; i < gasitLen ; i++ ) {
printf("%d ", gasit[i]);
}
/* int lung = strlen(pat);
for ( int i = 0; i < lung ; i++ )
printf("%d ", func[i]);
*/
// printf("%s -> %s",pat,text);
return 0;
}