1032. Sharing (25)

不念不忘少年蓝@ 2022-05-31 11:56 149阅读 0赞

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.

![1w_m16pjsommxz.jpg][]  
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:

*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

--------------------

题目大意：

为了存储英语单词，一种方法是使用链表，并以字母的形式储存单词。为了节省空间，如果它们有相同的后缀，我们可以让他们共享相同的子列表。例如“loading”和“being”存储在图1中。  
您的任务是找到公共后缀的起始位置（例如，图1中“i”的位置）。  
输入规格：  
每个输入文件包含一个测试用例。对于每种情况，第一行包括两个节点地址和一个正数N(<=10的5次方)，其中两个节点是两个单词的头节点地址，而N是节点的总数。一个节点的地址是一个5位的整数，空表示为-1。  
然后是N行，每一个节点的描述格式如下：  
地址 数据 下一个地址  
地址是节点的位置，数据是该节点包含的字母，它是由\{a-z, A-Z\}中选择的英文字母，下一个位置表示下一个节点的位置。  
输出规格：  
对于每种情况，只需输出公共后缀5位的起始位置。如果两个单词没有公共后缀，输出“-1”代替。

代码：

#include<stdio.h>
    struct node
    {
        int next;
        int cnt;
    }letter[100001];
    int main()
    {
        int i,j,n,m,k,t,l,a;
        scanf("%d %d %d",&n,&m,&k);
        a=n;
        for(i=0;i<k;i++)
        {
            scanf("%d %*s %d",&t,&l);
            letter[t].next=l;
        }
        while(n!=-1)
        {
            letter[n].cnt++;
            n=letter[n].next;
        }
        while(m!=-1)
        {
            if(letter[m].cnt==1)
                break;
            letter[m].cnt++;
            m=letter[m].next;
        }
        if(m==-1)
            printf("-1\n");
        else
        printf("%05d\n",m);
        return 0;
    }

[1w_m16pjsommxz.jpg]: http://nos.patest.cn/1w_m16pjsommxz.jpg