字符串核对

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

void table(char*);  // 建立前进表 
int search(int, char*, char*); // 搜寻关键字 
void substring(char*, char*, int, int); // 取出子字串 

int skip[256]; 

int main(void) { 
    char str_input[80]; 
    char str_key[80]; 
    char tmp[80] = {'\0'}; 
    int m, n, p; 

    printf("请输入字串："); 
    gets(str_input); 
    printf("请输入搜寻关键字："); 
    gets(str_key); 

    m = strlen(str_input); // 计算字串长度 
    n = strlen(str_key); 
    table(str_key);  
    p = search(n-1, str_input, str_key); 

    while(p != -1) { 
        substring(str_input, tmp, p, m); 
        printf("%s\n", tmp); 
        p = search(p+n+1, str_input, str_key); 
    } 

    printf("\n"); 

    return 0; 
} 

void table(char *key) { 
    int k, n; 

    n = strlen(key); 

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

int search(int p, char* input, char* key) { 
    int i, m, n; 
    char tmp[80] = {'\0'}; 

    m = strlen(input); 
    n = strlen(key); 

    while(p < m) { 
        substring(input, tmp, p-n+1, p); 
        
        if(!strcmp(tmp, key))  // 比较两字串是否相同 
           return p-n+1; 
        p += skip[input[p]]; 
    } 

    return -1; 
} 

void substring(char *text, char* tmp, int s, int e) { 
    int i, j; 

    for(i = s, j = 0; i <= e; i++, j++) 
        tmp[j] = text[i]; 

    tmp[j] = '\0'; 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringMatch {
    private int[] skip;
    private int p;
    private String str;
    private String key;
    
    public StringMatch(String key) {
        skip = new int[256];
        this.key = key;
        
        for(int k = 0; k <= 255; k++) 
            skip[k] = key.length(); 
        for(int k = 0; k < key.length() - 1; k++) 
            skip[key.charAt(k)] = key.length() - k - 1; 
    }
    
    public void search(String str) {
        this.str = str;
        p = search(key.length()-1, str, key);
    }
    
    private int search(int p, String input, String key) {   
        while(p < input.length()) { 
            String tmp = input.substring(
                                p-key.length()+1, p+1); 

            if(tmp.equals(key))  // 比较两字串是否相同 
               return p-key.length()+1; 
            p += skip[input.charAt(p)]; 
        } 

        return -1; 
    }
    
    public boolean hasNext() {
        return (p != -1);
    }
    
    public String next() {
        String tmp = str.substring(p);
        p = search(p+key.length()+1, str, key);
        return tmp;
    }
    
    public static void main(String[] args) 
                                      throws IOException {
        BufferedReader bufReader = 
            new BufferedReader(
                    new InputStreamReader(System.in));
        
        System.out.print("请输入字串：");
        String str = bufReader.readLine();
        System.out.print("请输入搜寻关键字："); 
        String key = bufReader.readLine();
        
        StringMatch strMatch = new StringMatch(key);
        strMatch.search(str);

        while(strMatch.hasNext()) { 
            System.out.println(strMatch.next()); 
        } 
    }
}