PAT甲级1032 Sharing (25分)|C++实现

一、题目描述

原题链接

Input Specification:

​​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

二、解题思路

一道基本的链表题，由于地址数字不大，我们可以用静态链表实现。给我们输入一些字符以及对应地址，给出两个字符串的首字符的地址，让我们判断它们有没有共用后缀，共用后缀的那个起点的字符地址是什么。那么我们可以首先把第一个字符串对应的链表建立起来，把该字符串中的所有字符都做一个“已存在”的标志，我这里是用flag数组实现。随后建立另一个字符串对应的链表，事实上，在这个过程中，只要碰到某个字符对应的flag是true，我们就可以直接输出该地址，如果建立完了链表都没有输出，则最后输出-1即可。

三、AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 100001;
vector<int> A, B;
int flag[maxn] = {0};
struct Node
{
    char ch;
    int next;
}node[maxn];
int main()
{
    int stA, stB, N, tmp;
    scanf("%d%d%d", &stA, &stB, &N);
    for(int i=0; i<N; i++)
    {
        scanf("%d", &tmp);
        scanf(" %c %d", &node[tmp].ch, &node[tmp].next);
    }
    tmp = stA;
    while(tmp != -1)
    {
        A.push_back(tmp);
        flag[tmp] = 1;
        tmp = node[tmp].next;
    }
    int ans = -1;
    tmp = stB;
    while(tmp != -1)
    {
        B.push_back(tmp);
        if(flag[tmp])
        {
            printf("%05d", tmp);
            return 0;
        }
        tmp = node[tmp].next;
    }
    printf("-1");
    return 0;
}