## 题目

1032 Sharing （25 分）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.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:

 ``````1 `````` ``````Address Data Next ``````

where`Address` 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:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````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:

 ``````1 `````` ``````67890 ``````

### Sample Input 2:

 ``````1 2 3 4 5 `````` ``````00001 00002 4 00001 a 10001 10001 s -1 00002 a 10002 10002 t -1 ``````

### Sample Output 2:

 ``````1 `````` ``````-1 ``````

## 代码

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 `````` ``````#include #include using namespace std; struct NODE { char data; int next; bool flag; }node[100000]; int main() { int a,b,m; scanf("%d %d %d",&a,&b,&m); for(int i=0;i

## 思路

• 静态链表
• 先遍历第一条链表，把flag置为1。再遍历第二条链表，若遇到flag为1的节点，即为common suffix
• printf("%05d",b)可以在不足5位的数字前补0，这会影响其中一个数据点。
Licensed under CC BY-NC-SA 4.0
Built with Hugo