c++解决PTA A1032(vector或hash)

c++解决PTA A1032(vector或hash)

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
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

储存英文单词，一种方式使用链表一个字符一个字符储存单词，为了节省空格，我们让单词共享相同的子串，如果他们有相同的前缀，举个例子，loading与being，可以像图片一样储存。

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

输入规格: 每个输入文件包含一个测试样例，针对每个样例第一行输入两个地址的节点，和一个正整数N，这两个地址是这两个单词的第一个节点的地址，以及N是总得节点数量，节点地址是五位正整数，以及NULL代表-1.N行这样描述节点，地址是节点的位置，数据是英文间单词的字符，以及text是下一个结点的地址。

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.

输出规格，对于每个测试样例，净输出五位共享前缀的开始地址，如果两个单词没有相同额后者会，输出-1

思路核心

检验公共前缀的地址，肯定要进行静态链表遍历。静态遍历一遍，从后往前判断，如果判断两个地址不等在跳出，如果有肯定减减了。

完整源码

#include
#include
#include
#include
using namespace std;
const int maxn = 100010;
struct node{
    char data;
    int next;
}n[maxn];
int main()
{
    int h1,h2,N;
    int i;
    cin >> h1>> h2>>N;
    while(N--){
        cin >> i >> n[i].data >> n[i].next;
    }
    vectorv1,v2;
    for(i=h1;i!=-1;i=n[i].next){
        v1.emplace_back(i);
    }
    for(i=h2;i!=-1;i=n[i].next){
        v2.emplace_back(i);
    }
    int j;
    for(i=v1.size()-1,j=v2.size()-1;i>=0&&j>=0&&v1[i]==v2[j];i--,j--);
    if(i==v1.size()-1){
        printf("-1");
    }else{
        printf("%05d",v1[i+1]);
    }
    return 0;
}

方法2直接使用hash

#include
#include
#include
#include
using namespace std;
const int maxn = 1000010;
struct node{
    char data;
    int next;
    bool flag;
}node[maxn];
int main()
{
    for(int i = 0;i> k >> node[k].data >> node[k].next;
    }
    int p;
    for(p=s1;p!=-1;p=node[p].next){
        node[p].flag = true;
    }
    for(p=s2;p!=-1;p=node[p].next){
        if(node[p].flag == true) break;//找到第一个已经在第一条链表中出现的结点
    }
    if(p != -1){//如果第二条链表还没有到达结尾，则说明找到了公用结点
        printf("%05dn",p);
    }else{
        printf("-1n");
    }
    return 0;
}