【PAT_1046】 Sharing (25)

题目描述：

找到word1和word2的公共后缀的起始位置

输入

第一行 地址一adress1（word1的起始地址），地址二（word2的起始地址），正整数（节点总数）。其中节点的地址是5位正整数，NULL由-1表示。
然后是N行，每行描述一个格式的节点：
Address Data Next
其中Address是节点的位置，Data是该节点包含的字母，它是从{a-z，A-Z}中选择的英文字母，Next是下一个节点的位置。

输出

输出公共后缀的起始位置。

解题思路

word1和word2的公共后缀的长度相同，所以从word1和word2长度相同的位置开始比较。先获得word1和word2的长度len1和len2，假设word1较word2长，先找到word1的第len2-len1个节点，是的word1余下长度与word2相同，然后逐一比较word1和word2的各节点的下一个地址是否相等，相同即返回。

代码

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

struct node {

    char val;
    int next;
}nodes[100000];
int main() {
    int chain1, chain2, n;
    int adress, next;
    char val;
    cin >> chain1 >> chain2 >> n;
    for (int i = 0; i < n; i++) {
        cin >> adress;
        cin >> val;
        cin >> next;

        nodes[adress].val = val;
        nodes[adress].next = next;
    }
    //int  chain1,j
    bool flag = true;
    int c2=chain2,c1 = chain1;
    int len1=1,len2=1;
    while(nodes[c2].next != -1){
        c2 = nodes[c2].next;
        len2++;
    }
    while(nodes[c1].next != -1){
        c1 = nodes[c1].next;
        len1++;
    }
    while(len1>len2){
         chain1 = nodes[chain1].next;
         len1--;
    }
    while(len1<len2){
         chain2 = nodes[chain2].next;
         len2--;
    }
    while(nodes[chain1].next != -1&&nodes[chain2].next != -1 ){

        //cout<<chain1<<","<<chain2<<endl;
        if (chain1 == chain2) {
            cout.fill('0');
            cout.width(5);
            cout << chain1 << endl;
            flag = false;
            break;
        }

       chain2 = nodes[chain2].next;
        chain1 = nodes[chain1].next;
    }
    if(flag)
        cout<<"-1"<<endl;


    return 0;
}