DS作业-5-22网安物联网-20231016

作业ch4-1：

（1）

从主串S的第一个字符’a’开始，与模式串T的第一个字符’b’进行比较，发现不相等。

从主串S的第二个字符’b’开始，与模式串T进行比较，发现前三个字符’b’, ‘a’, 'b’相等，但第四个字符’a’与模式串T的第四个字符’b’不相等。

从主串S的第三个字符’c’开始，与模式串T进行比较，发现第一个字符不相等。

以此类推，直到从主串S的第12个字符’b’开始，与模式串T进行比较，发现五个字符’b’, ‘a’, ‘b’, ‘a’, 'b’全部相等，说明找到了一个匹配。

所以位置是12

（2）

j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
T[j]	a	b	c	a	a	b	b	c	a	a	a	b	a	b	a	b	a	a	b	c	a
next[j]	-1	0	0	0	1	1	2	0	0	1	1	1	2	1	2	1	2	1	1	2	0

（3）

S[0]与T[0]不匹配，移动模式串到S[1]。

S[1]与T[0]不匹配，移动模式串到S[2]。

以此类推，一直到S[4]和T[0]不匹配

移动模式串到S[1]

以此类推，当遇到不匹配时，回退到T[next[j]]的位置

作业ch4-2：

Status AddSMatrix(TSMatrix &C, TSMatrix A, TSMatrix B) {
  C.mu = A.mu;
  C.nu = A.nu;
  int i = 0, m = 0, n = 0;
  while (m < A.tu && n < B.tu) {
    if (A.data[m].row < B.data[n].row) {
      C.data[i] = A.data[m];
      i++;
      m++;
    } else if (A.data[m].row > B.data[n].row) {
      C.data[i] = B.data[n];
      i++;
      n++;
    } else if (A.data[m].row == B.data[n].row) {
      if (A.data[m].col == B.data[n].col) {
        C.data[i].item = A.data[m].item + B.data[n].item;
        C.data[i].row = A.data[m].row;
        C.data[i].col = A.data[m].col;
        m++;
        n++;
        i++;
      } else if (A.data[m].col > B.data[n].col) {
        C.data[i] = B.data[n];
        i++;
        n++;
      } else if (A.data[m].col < B.data[n].col) {
        C.data[i] = A.data[m];
        i++;
        m++;
      }
    }
  }
  C.tu = i + 1;
}