タイトルの説明

丁姉さんは最近LCS(The longest common substring)に夢中になりました!今日彼女は他のものを探して遊びたいと思って、そこで彼女は2つの文字列AとBを見つけて、今彼女はそれらの末尾の接続が形成した最も長い文字列を知りたいと思って、例えばA=abc、B=bcaはAの末尾から、A列のbcはB列のbcの末尾と接続します.

説明を入力:

入力データは複数のテストサンプルを含み、各テストサンプルは2行を占め、第1行は文字列A、第2行は文字列Bであり、各文字列の長さが1010を超えないことを保証する.

出力の説明:

AとBの末尾に接続された最長文字列は、テストインスタンスごとに1行出力され、2つの文字列が接続されていない場合は「NULL!」が出力されます.(引用符を含む).

例

入力

abc bca wad ad as asd wa aw wa wwa

しゅつりょく

bc ad as a “NULL!”

考え方:

まず簡単な問題で、最長のマッチング前接尾辞リンクを探すことを意味するので、Sから最初のマッチング文字を探して順番に判断するだけです.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#define PI 3.1415926535
#define MAX 10005
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define fori(a,b) for(int i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof(a))
#define BASE 10000
#define BASE 10000
using namespace std;
typedef long long ll;
const int maxn=1e15+5;
using namespace std;
typedef struct fract fract;
char a[1011],b[1011];
int main()
{
        ll i,k;
        ll  l,m,n,x,y,z,sum,num;
    while(cin>>a>>b)
    {
        int j=0;
        x=strlen(a);
        y=strlen(b);
        for(i=0;i<x;i++)
        {
            if(a[i]==b[j])
                j++;
            else
                j=0;
        }
        if(!j)
        {
            printf("\"NULL!\"
");
            continue;
        }
        for(i=0;i<j;i++)
        {
            printf("%c",b[i]);
        }
        cout<<endl;
    }
}

この問題は長い間考えてから提出したが、当時は更新が続いているかどうかを考えていたので、後で考えては存在しない.