严蔚敏老师的课件(总结.ppt)

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.22M 资料格式：ppt 举报版权申诉

bfliu_06-478073-4744300845208059894.ppt.pdf-第1页.png

第1页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第2页.png

第2页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第3页.png

第3页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第4页.png

第4页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第5页.png

第5页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第6页.png

第6页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第7页.png

第7页 / 共29页

bfliu_06-478073-4744300845208059894.ppt.pdf-第8页.png

第8页 / 共29页

文本预览

4.28 链表结构的串的 next 函数 j 1 3 模式串 a b a 1 next函数值 0 2 1 5 4 6 a b c 3 2 2  a b a a b c  结点结构: next chdata succ

void get_next(char T[], int next[]) { k = -1; j = 0; next[0] = -1; k = -1; j = 0; next[0] = -1; q=T.head; p=q->succ; p->next=q; ( T[j+1] != \0) while ( T[j+1] != \0) { ( p->succ!=NULL ) ( k = = -1 || T[j] ==T[k] ) if ( k = = -1 || T[j] ==T[k] ) ( q==T.head || p->chdata == q->chdata ) { ++j; ++k; next[j] = k; } { ++j; ++k; next[j] = k; } { p=p->succ; q=q->succ; p->next=q; } k = next[k]; else k = next[k]; q=q->next; } } // get_next

void get_nextval(LString T) { q = T.head; p = q->succ; p->next = q; while (p->succ) { if ( q==T.head || p->chdata == q->chdata ) { p = p->succ; q = q->succ; if ( p->chdata == q->chdata ) p->next = q->next; else p->next = q; } else q = q->next; } }

4.30 求串 S 中出现的第一个最长重复子串及其位置。所谓“重复子串”指的是， SubString(S, i, len) == SubString(S, j, len) 其中: 1≤ i

分析: 此题可有两种解法一种比较直观的做法是: 在串 S 中取子串 SubString( S, i, len ) 和子串 SubString( S, i+1, StrLength(S)-i ) 相匹配。假设 S 串的长度为 n, 则 len 的变化范围是从 n-1 到 1 , i 的变化范围是从 1 到 n - len 最坏情况下的时间复杂度为 O(n3)。

另一种作法是，利用 next 函数的特性，可使算法的时间复杂度减至 O(n2)。 next[j]0 表示: 在第 j 个字符之前存在一个长度为 next[j] 的重复子串。由此，算法的基本思想为: 求各子串 pat[i] = SubString(S, i, StrLength(S)-i+1) 的next 函数值，i=1, 2, …, StrLength(S)-1 ，并从中求得最大值

例如: S = abaabaaabaaaab pat[1] a b a a b a a a b a a a a b next值 -1 0 0 1 1 2 3 4 1 2 3 4 1 1 b a a b a a a b a a a a b -1 0 0 0 1 2 3 0 1 2 3 0 0 a a b a a a b a a a a b -1 0 1 0 1 2 2 3 4 5 6 2 a b a a a b a a a a b -1 0 0 1 1 1 2 3 4 5 1 b a a a b a a a a b -1 0 0 0 0 1 2 3 4 0 pat[2] next值 pat[3] next值 pat[4] next值 pat[5] next值

i = 1; maxl = 0; n = StringLength(S); while ( n-i+1 > maxl ) { 求 pat[i] = SubString( S, i, n-i+1 ) 的 next[j]中的最大值; len = Max(next[j]) ; if (len==next[n-1] && S[n-1]==S[i+len-1]) len++; if ( len > maxl ) { maxl = len; 记下子串pat[i] 的起始位置 i; } i++; }

分享到：

赞收藏

资料库

严蔚敏老师的课件(总结.ppt)

相关推荐

开发技术

热门标签

最新资料