假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀空间。设str1和str2分别指向两个单词所在单链表的头结点,请实现一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置的结点,输出该结点对应的字符。
时间: 2024-05-16 10:12:35 浏览: 31
算法思路:
1.首先遍历str1,记录下str1的长度len1和最后一个节点p1。
2.同理,遍历str2,记录下str2的长度len2和最后一个节点p2。
3.比较p1和p2是否相同,若不同则说明两个单词没有共同后缀,直接返回NULL。
4.若相同,则从str1和str2的尾部开始向前遍历,直到遇到第一个不相同的节点为止,该节点的下一个节点即为共同后缀的起始位置。
代码实现:
```
typedef struct ListNode{
char data;
struct ListNode *next;
}ListNode, *LinkList;
ListNode *findCommonSuffix(LinkList str1, LinkList str2){
int len1 = 0, len2 = 0;
ListNode *p1 = str1->next, *p2 = str2->next;
while(p1){
len1++;
if(p1->next == NULL) break;
p1 = p1->next;
}
while(p2){
len2++;
if(p2->next == NULL) break;
p2 = p2->next;
}
if(p1 != p2) return NULL;//判断两个单词是否有相同的后缀
p1 = str1->next;
p2 = str2->next;
int k = len1 - len2;
if(k > 0){
for(int i = 0; i < k; i++)
p1 = p1->next;
}
else{
for(int i = 0; i < -k; i++)
p2 = p2->next;
}
while(p1 && p2){
if(p1 == p2) return p1->next;
p1 = p1->next;
p2 = p2->next;
}
return NULL;
}
```
时间复杂度:$O(n)$,其中$n$为两个单词中较短的那个的长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)