【ZSTU 4212 2015年12月浙理工校試合C】【ゲームKMP or strncmp】String Game文字列前後に数人を取り、最後に残ったものがテンプレート列である可能性があるかどうかを順番に見る

4212: String Game
Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 334  
Solved: 40
Description
Alice and Bob are playing the following game with strings of letters.
Before the game begins, an initial string and a target string are decided. The initial string is at least as long as the target string. Then, Alice and Bob take turns, starting with the initial string. Bob goes first. In each turn, the current player removes either the first or the last letter of the current string. Once the length of the current string becomes equal to the length of the target string, the game stops. If the string at the end of the game is equal to the target string, Alice wins the game; otherwise Bob wins.
Determine who will win the game if both players are playing optimally.
Input
Each test case starts with N, the number of inputs to process. Each input consists of one line, which contains the initial string, followed by a space, followed by the target string. Each string consists of only lowercase letters. The total input length will be less than 500000 characters.
Output
For each input, output the winner, which will either be Alice or Bob.
Sample Input

5
aba b
bab b
aaab aab
xyz mnk
xyz xyz

Sample Output

Alice
Alice
Bob
Bob
Alice

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=5e5+10,M=0,Z=1e9+7,ms=0x3f3f3f3f;
int casenum,casei;
int n,m;
char a[N],b[N];
bool solve()
{
	int bef=(n-m)/2;
	int beh=n-m-bef;
	if(bef==beh)
	{
		if(strncmp(b+1,a+bef+1,m)==0)return 1;
		if(strncmp(b+1,a+bef,m)==0
		 &&strncmp(b+1,a+bef+2,m)==0)return 1;
	}
	else
	{
		if(strncmp(b+1,a+bef+1,m)==0
		 &&strncmp(b+1,a+bef+2,m)==0)return 1;
	}
	return 0;
}
int main()
{
    scanf("%d",&casenum);
    for(casei=1;casei<=casenum;++casei)
    {
		scanf("%s",a+1);n=strlen(a+1);
		scanf("%s",b+1);m=strlen(b+1);
		puts(solve()?"Alice":"Bob");
    }
    return 0;
}
/*
【  】
     a b，5e5>=|a|>=|b|
Alice Bob    ，Bob  。
      a        ，    ，  |a|==|b|
           b ，  Alice ，  Bob 。
          ，        。

【  】
   KMP or strncpy

【  】
  ，           ，  a     b ，    Bob 。
          ，       KMP  。

    ，Alice       Bob " " ，  Bob           ，    。
  ，    Bob。  Bob       ，         。
  Bob      ，                ，  Bob    ，     。
  ，  Bob      ，               ，Bob    ？
   Alice          ，Alice     ，    Bob ？
       ，    {aabaaaaba b}，         ，        AC。

      ，                。
                ——

1，             ，    Alice Bob      。
      ，Alice                 ，          ，       （     ）
														   1   1（          Bob）。
    ，              ，Alice    。
  ，      1   1       ，Alice        。  Bob         。

2，            ，    Bob Alice      。
      ，Alice          ，           （           ，          Bob）。
    ，                      ，  Alice         。

    ，         （        ）         ，
  ——          ，Alice              ？
 ，             ，Alice          ？

      ，      。
    ？   Alice  Bob，               ，Bob Alice           。
   1 ，Alice        1   1，     Bob  
   2 ，Alice        。

  ，              。  KMP    。

【     &&  】
O（n）

*/