2013年9月11日 星期三

[C/C++ 演算法]- 字串核對

[C/C++ 演算法]- 字串核對



剛才找資料時發現一個C/C++的教學網站,趕快發揮(C/P)的長才將它備份來,有需要的同好,歡迎來(C/P)一下^^。


拷貝來源:
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/MatchString.htm









#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#define SKIP_TABLE_SIZE 256
#define STRING_LENGTH 80

void
table(int*, char*); // 建立前進表
int indexOf(int*, int, char*, char*); // 搜尋關鍵字
void subString(char*, char*, int, int); // 取出子字串

int
main(void) {
int
skip[SKIP_TABLE_SIZE];

char
input[STRING_LENGTH];
char
key[STRING_LENGTH];
char
sub[STRING_LENGTH] = {'\0'};

printf("字串:");
gets(input);
printf("關鍵字:");
gets(key);

table(skip, key);

int
m = strlen(input); // 計算字串長度
int n = strlen(key);
int
p = indexOf(skip, n - 1, input, key);

while
(p != -1) {
subString(input, sub, p, m);
printf("%s\n", sub);
p = indexOf(skip, p + n + 1, input, key);
}


return
0;
}


void
table(int* skip, char *key) {
int
n = strlen(key);
int
k;
for
(k = 0; k < SKIP_TABLE_SIZE; k++) {
skip[k] = n;
}

for
(k = 0; k < n - 1; k++) {
skip[key[k]] = n - k - 1;
}
}


int
indexOf(int* skip, int from, char* str, char* key) {
char
sub[STRING_LENGTH] = {'\0'};

int
strLen = strlen(str);
int
keyLen = strlen(key);
int
index = from;

while
(index < strLen) {
subString(str, sub, index - keyLen + 1, index);
if
(!strcmp(sub, key)) { // 比較兩字串是否相同
return index - keyLen + 1;
}

index += skip[str[index]];
}


return
-1;
}


void
subString(char *text, char* sub, int s, int e) {
int
i, j;
for
(i = s, j = 0; i <= e; i++, j++) {
sub[j] = text[i];
}

sub[j] = '\0';
}


 


沒有留言:

張貼留言