Orderly Class

题目大意：给出两个长度相同的不同字符串A, B.可以对A的任意长度区间进行一次翻转，问有多少种方法可以使得翻转后两字符串相同。

思路：

1.一开始我是利用string以及algorithm头文件里的reverse()来做的，毫无疑问超时了。其实我知道这种题目一定是有什么特定的算法或者思路。很可惜第一次遇到我不会。

2.正解是找到A，B两串第一个不相等字符的左边界以及右边界，将A字符串中这区间翻转后进行判断是否A，B相等，若不相等答案为0。若相等，那么答案更新为1，然后在A串左边界向左，右边界向右，判断是否字符相等，相等的话ans++，不等的话break出答案。

代码如下：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int MAXN = 1e5 + 100;
 4 
 5 char s1[MAXN], s2[MAXN], temp[MAXN];
 6 int left, right;
 7 
 8 int main()
 9 {
10     int ans = 0;
11     scanf("%s%s", s1, s2);
12     int len = strlen(s1);
13     for(int i = 0; i < len; i ++)
14         if(s1[i] != s2[i])
15         {
16             left = i;
17             break;
18         }
19     for(int i = len - 1; i >= 0; i --)
20         
21         if(s1[i] != s2[i])
22         {
23             right = i;
24             break;
25         }
26     if(left == right)
27         printf("0
");
28     else
29     {
30         strcpy(temp, s1);
31         int r = right;
32         for(int i = left; i <= right; i ++)
33         {
34             s1[i] = temp[r];
35             r --;
36         }
37         if(strcmp(s1, s2) != 0)
38             printf("0
");
39         else
40         {
41             ans ++;
42             left --, right ++;
43             while(left >= 0 && right < len)
44             {
45                 if(s1[left] == s1[right])
46                 {
47                     ans ++;
48                     left --;
49                     right ++;
50                 }
51                 else
52                     break;
53             }
54             printf("%d
", ans);
55         }
56     }
57     return 0;
58 }

View Code