To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.
Figure 1
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105 ), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
给出两个单词，每个单词都是以链表的形式存储，链表每个节点存储一个字符，然后指向下一个节点，最后一个节点指向NULL（以-1代替）
输入 给出了每个节点的地址、内容、指向下一个节点的地址
要求找到两个单词的共同后缀的第一个字符的地址（比如loading和being就应该输出字符i的地址），如果不存在公共后缀，输出 -1。
思路分析1. 自以为是的错误思路（自闭的一下午的开始，如果不感兴趣可以直接看下面正确思路）
刚开始我是这样想的： 既然是两个单词的公共部分，所以要找的那个地址一定是在所有给定的<Address Data NextAddress>格式数据中，在 NextAddress位置出现了两次的，而且是唯一出现了两次的，因为后面再一样的也不会再给出。
(如果两个单词的某个节点的nextAddress都指向了同一个地址，那么后续肯定就一样了，比如loading的d指向了i，being的e指向了i，所以i就是他们共同后缀的开始，这也就是为什么我统计的是<Address Data NextAddress>中NextAddress出现的次数)
比如题目中 loading 和 being 的 样例第一组，可以看到只有 i 对应的 67890 地址出现了两次。
所以，直接开一个大于 100000 的一维数组 count[]，用节点地址做下标。 每次得到一个 <Address Data Next> 数据，令 count[NextAddres]++; 最后遍历一遍，若 count[i] == 2 则 i 即为所求。
因为这个思路记录的是每次的 NextAddress，所以如果第一个字母就是一样的（比如abcdh和agjkl），那么就没有类似count[beginAddress]++操作。所以代码中补充一下，如果题目给定的两个起始地址相同，则直接输出这个起始地址。
怎么样，看到现在是不是觉得我分析的很有道理，而且代码写起来也很简单
#include <iostream> using namespace std; // 这种写法 对于 loading ing 会输出 -1，正确应该输出 i 的地址 int main() { int s1, s2, n; cin >> s1 >> s2 >> n; int count[100000] = {0}; // 针对第一个地址就相同的情况 if (s1 == s2) { printf("%05d", s1); return 0; } int id; char data; int nextid; for (int i = 0; i < n; ++i) { cin >> id >> data >> nextid; if (nextid == -1) continue; // id data next统计了出现了两次的next count[nextid]++; } // 写法二 // 找到第一个出现次数大于1的地址（因为只有一个地址会出现2次），直接输出并返回 for (int i = 0; i < 100000 ;++i) { if (count[i] > 1) { printf("%05d", i); return 0; } } // 没找到就输出 -1 printf("-1"); // 写法二 // 找到了也不急着输出，全部遍历完了输出 // int ans = -1; // for (int i = 0; i < 100000 ;++i) { // if (count[i] > 1) { // ans = i; // } // } // ans == -1 ? printf("-1") : printf("%05d", ans); return 0; }你可以看到我的代码下半部分是有两种写法的，总结来说就是
第一中写法，找到的是count数组中第一个出现了2次的地址，直接输出。
第二种写法，找到的是count数组中最后一个出现了2次的地址，遍历完了再输出。