九度OJ1468

这道题其实就是个很简单的静态链表，需要注意的是，地址一共有5位，最后输出的时候如果之前是使用int类型存储地址的话，一定要强制规定输出的位数（5位），否则有可能会将高位省略。（如地址00001输出为1）

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include<string>

#include<iostream>

using namespace std;

int next[100001];

char letter[100001];

char str1[200001],str2[200001];

int add1[200001],add2[200001];

void caladd(string s,int&add)

{

    if(s=="NULL")

        add=-1;

    else if(s=="-1")

        add=-1;

    else

        add=(s[0]-'0')*10000+(s[1]-'0')*1000+(s[2]-'0')*100+(s[3]-'0')*10+(s[4]-'0');

}

int main()

{

    int start1,start2,n,i,j,top1,top2;

    string s1,s2;

    while(cin>>s1>>s2>>n)

    {

        start1=0;

        start2=0;

        memset(next,-1,sizeof(next));

        memset(letter,0,sizeof(letter));

        caladd(s1,start1);

        caladd(s2,start2);

        if(start1==-1||start2==-1)

        {

            printf("-1\n");

            continue;

        }

        for(i=1;i<=n;i++)

        {

            char c;

            string a1,b1;

            int a,b;

            cin>>a1>>c>>b1;

            caladd(a1,a);

            caladd(b1,b);

            next[a]=b;

            letter[a]=c;

        }

        i=start1;

        top1=0;top2=0;

        while(i!=-1)

        {

            add1[top1]=i;

            str1[top1++]=letter[i];

            i=next[i];

        }

        str1[top1]=0;

        i=start2;

        while(i!=-1)

        {

            add2[top2]=i;

            str2[top2++]=letter[i];

            i=next[i];

        }

        str2[top2]=0;

        int l1=top1-1,l2=top2-1;

        while(str1[l1]==str2[l2]&&l1>0&&l2>0)

        {

            l1--;l2--;

        }

        if(l1==top1-1)

        printf("-1\n");

        else

        printf("%05d\n",add1[l1+1]);//这个地方非常重要，留此以为警戒

    }

    return 0;

}