Description

栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个进栈的数据被第一个读出来）

给出两个字符串s1和s2，请判断s1能否通过栈的模拟（即进栈和出栈）得到s2？

Input

输入有多组测试数据，每组输入占两行，s1和s2各占一行。为了简化问题，s1和s2保证仅由小写字母组成，不会出现其它字符；s1和s2等长，且长度不大于100；s2是s1的一种排列，不会在s2中出现s1里没有的字符

Output

对于每组输入，输出仅占一行，如果s1能通过栈的模拟得到s2，则输出“YES”；否则输出“NO”

Sample Input

abcde

baedc

bjfuacm

fujcbma

Sample Output

YES

NO

分析：关于栈有一个很有用的性质，对于出栈序列的每一个元素，该元素后比该元素先入栈的一定按照降序排列。若入栈的是一串数字例如12345，则21435是一个合法的出栈顺序，每一个元素i后比i小的都是降序排列（因为入栈的数字代表了进栈先后），24153不是合法的，因为对于4，比它小的1和3的顺序不对。

1 #include 
     
        2 #include 
      
        3 using namespace std; 4 int main() 5 { 6     string s1, s2; 7     while (cin >> s1 >> s2) 8     { 9         int n = s1.size();10         int a1[n], a2[n];            //把字母转换成数字处理11         for (int i = 0; i < n; ++i)12         {13             a1[i] = i;14             a2[i] = s1.find(s2[i]);15         }16         int min; bool existless, islegal;17         for (int i = 0; i < n; ++i)18         {19             min = a2[i];20             existless = 0;21             int j;22             for (j = i + 1; j < n; ++j)23                 if (a2[j] < a2[i])       //是否存在比a[i]小的值24                 {25                     min = a2[j];26                     existless = 1;27                     break;28                 }29             islegal = 1;30             if (existless)31             {32                 for (int k = j + 1; k < n; ++k)33                     if (a2[k] < a2[i])34                     {35                         if (a2[k] < min)36                             min = a2[k];    //更新min37                         else38                         {39                             islegal = 0;40                             break;41                         }42                     }43             }44             if (!islegal)45             {    printf("NO\n");    break;    }46         }47         if (islegal)48         printf("YES\n");49     }50     system("pause");51     return 0;52 }