pat

题目

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.

Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive $N (≤10^5)$, 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

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:

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

这题不用想得太复杂，因为已知两个序列是后缀相同的（如果存在的话），不需要考虑太多。就直接从一个点出发遍历序列，标记走过的位置，然后再从另一个点出发往下遍历序列，若走到标记过的位置，则停止。

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

#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> vi;
int V[100005];
bool vstX[100005], vstY[100005];
vi X, Y;
int (){
    int fir_add, sec_add, N, tadd, tnext;
    char tw;
    scanf("%d %d %d", &fir_add, &sec_add, &N);
    fill(V, V + 100005, -1);
    fill(vstX, vstX + 100005, false);
    fill(vstY, vstY + 100005, false);
    for(int i = 0;i < N;i++){
        scanf("%d %c %d", &tadd, &tw, &tnext);
        V[tadd] = tnext;
    }
    for(int i = fir_add; i != -1; i = V[i]){
        vstX[i] = true;
    }
    for(int i = sec_add; i != -1;i = V[i]){
        if(vstX[i]){
      printf("%05d", i);
     return 0;
   }
    }
    printf("-1");
    return 0;
}