Spoj-NPC2015A Eefun Guessing Words

Eefun Guessing Words

Eefun is currently learning to read. His way of learning is unique, by trying to make every possible substring from a given string. However, when the string becomes longer, he can no longer remember all the substring. His friends want to test Eefun's skill by asking questions, given a string S, is there any substring that begins with letter X and ends with letter Y? According to Eefun, each substring contains at least 2 letters. As the given string S is pretty big, Eefun need your help to answer his friend's questions

Input

First line of input contain a single string S which was given by his friends.
Second line contain a number N, the number of questions that Eefun's friends ask.
Next N lines each consists of 2 characters, X and Y

Output

For each questions, output a single string "YA" if the substring exists, or "TIDAK" otherwise
(YA means yes and TIDAK means no in Indonesian)

Example

Input:

HALO
4
H O
L O
A O
O L

Output:

YA
YA
YA
TIDAK

Constraints:

'A' ≤ X,Y ≤ 'Z'
1 ≤ |S| ≤ 1.000.000
1 ≤ N ≤ 1.000.000

记一下每个字母第一次和最后一次出现的位置就好了

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<set>

 #include<map>

 #include<ctime>

 #define LL long long

 #define inf 0x7ffffff

 #define pa pair<int,int>

 #define mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 #define mod 100007

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int fst[],lst[];

 char s[],x,y;

 int n,q;

 int main()

 {

     while (~scanf("%s",s+))

     {

         memset(fst,,sizeof(fst));

         memset(lst,,sizeof(lst));

         n=strlen(s+);

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

         {

             if (!fst[s[i]])fst[s[i]]=i;

             lst[s[i]]=i;

         }

         q=read();

         for (int i=;i<=q;i++)

         {

             scanf(" %c %c",&x,&y);

             if (fst[x]&&fst[y]&&fst[x]<lst[y])puts("YA");

             else puts("TIDAK");

         }

     }

 }

Spoj NPC2015A

巴特西

Spoj-NPC2015A Eefun Guessing Words

Input

Output

Example

Constraints:

最新文章

热门文章