《数据结构》串

1
2
3
4
5
6
7

#define MAXLEN 255
typedef struct
{
    char ch[MAXLEN];
    int length;
}SString;

1
2
3
4
5
6

typedef struct
{
    char *ch;
    int length;
}SString;

 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

int Index_BF(string s, string t)
{
    int i = 1, j = 1;
    int lens = s.length();
    int lent = t.length();
    while(i < lens && j < lent)
    {
        if(s[i] == t[j])
        {
            i++,j++;
            continue;
        }
        else
        {
            i = i - j + 2;//i指示主串S正在比较的字符位置
            j = 1;//j指示子串t正在比较的字符位置
        }
    }
    if (j == lent)
    {
        return i - j;
    }
    return -1;
}

 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

void get_next(String T , int next[])//计算next数组
{
    int i =1,j = 0;
    next[1] = 0;
    while( i < T.length)
    {
        if( j ==0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int Index_KMP(String S,String T,int next[])
{
    int i = 1, j = 1;
    while(i <= S.length && j <= T.length)//i永远不递减
    if ( j==0 || S.ch[i] == T.ch[j])//字符匹配成功，指针后移
    {
        ++i;
        ++j;
    }
    else //字符匹配失败，根据next跳过前面的一些字符
    {
        j = next[j];
    }
    if(j > T.length)//匹配
        return i - T.length;
    else
        return 0;
}