• 任務描述
• 編程要求
  • 輸入
  • 輸出
• 測試說明
• 來源

---

任務描述

本關任務：假定采用帶頭結點的單鏈表保存單詞，當兩個單詞有相同的后綴時，則可共享相同的后綴空間。 例如，“loading”和“being”的存儲映像如下圖所示：

設str1和str2分別指向兩個單詞所在單鏈表的頭結點，請實現一個時間上盡可能高效的算法，找出由str1和str2所指的兩個鏈表共同后綴的起始位置的結點，輸出該結點對應的字符（如圖中的字符i）。

編程要求

輸入

多組數據，每組數據有三行，第一行為鏈表str1和str2的長度n和m，第二行為鏈表str1的n個元素，第三行為鏈表str2的m個元素（元素之間用空格分隔）。n=0且m=0時輸入結束。

輸出

對于每組數據輸出一行，為共同后綴的起始位置結點對應的字符。

測試說明

平臺會對你編寫的代碼進行測試：

測試輸入： 7 5 l o a d i n g b e i n g 7 9 f l u e n c y f r e q u e n c y 0 0

預期輸出： i u

來源

BJFUOJ

---

?

開始你的任務吧，祝你成功！

筆者第一次執行時，漏寫了count++。結果是無論如何打印都為空，甚至在函數開頭寫cout<<1;? 都仍然是打印空。筆者并未解決這個不算問題的問題

#include <iostream>
using namespace std;
typedef struct LNode
{char data;struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法創建單鏈表L=new LNode;L->next=NULL;LinkList r=L;for(int i=0;i<n;i++){LinkList p=new LNode;cin>>p->data;p->next=NULL;r->next=p;r=p;}
}
void FindSuffix(LinkList str1, LinkList str2,int n,int m)
{//查找兩個單詞鏈表共同后綴的起始結點/**************begin************/LinkList p,q;if(n>m) //p始終為更長那個的工作指針{p=str1->next;q=str2->next;}else {q=str1->next;p=str2->next;}
int diff=n-m;
if(diff<0) diff=diff*(-1);
int count=0;
while(count<diff)
{p=p->next;count++;
}
while(p&&q)
{if(p->data==q->data){cout<<p->data<<endl;break;}p=p->next;q=q->next;
}/**************end************/
}
int main()
{int n,m;while(cin>>n>>m){if(n==0&&m==0) break;LinkList str1,str2,p;CreateList_R(str1,n);CreateList_R(str2,m);FindSuffix(str1,str2,n,m);}return 0;
}