PAT-A1032 Sharing【链表】

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.

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

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

---

 

  设计思想：

 两个单词因为部分相同，所以在子串开始位置使用指针共享后面的内容。那么也就是说，从子串开始，到每个单词的最后面，所有的单词对应的位置都i应该是相同的字母。

所以想法来了，再宅

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int stu[100001];
int main(){
	int add1,add2,n;
	int start,end;
	char c;
	fill(stu,stu+100001,0);
	scanf("%d %d %d",&add1,&add2,&n);
	while(n--){
		scanf("%d %c %d",&start,&c,&end);    //保存节点
	    stu[start]=end;
	}
	vector<int> one;
	vector<int> two;
	int index=add1;               //摘出第一个节点
	while( index!=-1){
		one.push_back(index);      
		index=stu[index];
	}
	index=add2;
	while(index!=-1){
		two.push_back(index);      //摘出第二个节点。
		index=stu[index];
	}
		int l1=one.size();
	int l2=two.size();
	int i=0,j=0;
	if(l1>l2){
		i+=l1-l2;                  //下标对齐
	}
	else{
		j+=l2-l1;
	}
	while(i<l1&&j<l2&&one[i]!=two[j]){
		i++;
		j++;
	}
	if(i<l1&&j<l2&&one[i]==two[j]){
		printf("%05d\n",one[i]);
	}
	else{
		cout<<"-1"<<endl;
	}
    /*
    for(int i=0;i<l1;i++){
        for(int j=0;j<l2;j++){
            if(one[i]==two[j]){
                printf("%05d",one[i]);
                return 0;
            }
        }
    }
    cout<<-1;
   */
	 
	

	return 0;
}

 

Tips:

 1.一开始部分样例没过，是忽略掉了这么一个情况，就是两个单词完全一样

   我在保存单词的时候自动忽略了第一个字母，因为我理所当然的觉得两个单词相同是不会出现的

  不得不说，姥姥的测试样例短小精悍。

 2.在摘出了单词之后，就面临着找第一个相同的字母的问题了。

  其实你仔细想想，在这么一个系统中，因为单词的每个字母的起始位置都固定，只要碰到第一个共有的字母，那么这就是子串  的 开始，所以按照思想设计了注释的算法，很显然，因为算法时间O（n²），所以超时了，借鉴了大神的算法。

算法思路：

对齐，假设两个单词有公共子串，那么把他们右对齐之后，后面的子串部分每位字母都是一样的，但是两个子串长度不一定相同，因此要找齐，找齐的长度就是两个子串长度之差，从找齐位置开始往后依次比较，如果某一位相同，那么以后的所有都相同。结束循环