题意:忽略字母外的符号和大小写,求连续最长回文子串(n<=20000)。
O(n^2)方法
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4
5 #define N 20010
6
7 char s1[N], s2[N], s[N];
8 int dp[4][N], flag[N];
9
10 int is_other(char x)
11 {
12 if(x>='A'&&x<='Z' || x>='a'&&x<='z')
13 return 0;
14 return 1;
15 }
16
17 int is_good(char x, char y)
18 {
19 if(x<'a')
20 x += 'a' - 'A';
21 if(y<'a')
22 y += 'a' - 'A';
23 if(x==y)
24 return 1;
25 return 0;
26 }
27
28 int main()
29 {
30 FILE *fin = fopen("calfflac.in","r");
31 FILE *fout = fopen("calfflac.out", "w");
32
33 char ch;
34 int len = 0, len1 = 0;
35 while((ch = fgetc(fin))!=EOF)
36 s[len++] = ch;
37 for(int i=0; i<len; i++)
38 {
39 if(is_other(s[i])==1)
40 continue;
41 s1[len1] = s[i];
42 flag[len1] = i;
43 if(s[i]>='a' && s[i]<='z')
44 s1[len1] -= 'a' - 'A';
45 len1++;
46 }
47 for(int i=0; i<len1; i++)
48 s2[i] = s1[len1 - i - 1];
49 s1[len1] = '
2 #include <cstring>
3 #include <cstdlib>
4
5 #define N 20010
6
7 char s1[N], s2[N], s[N];
8 int dp[4][N], flag[N];
9
10 int is_other(char x)
11 {
12 if(x>='A'&&x<='Z' || x>='a'&&x<='z')
13 return 0;
14 return 1;
15 }
16
17 int is_good(char x, char y)
18 {
19 if(x<'a')
20 x += 'a' - 'A';
21 if(y<'a')
22 y += 'a' - 'A';
23 if(x==y)
24 return 1;
25 return 0;
26 }
27
28 int main()
29 {
30 FILE *fin = fopen("calfflac.in","r");
31 FILE *fout = fopen("calfflac.out", "w");
32
33 char ch;
34 int len = 0, len1 = 0;
35 while((ch = fgetc(fin))!=EOF)
36 s[len++] = ch;
37 for(int i=0; i<len; i++)
38 {
39 if(is_other(s[i])==1)
40 continue;
41 s1[len1] = s[i];
42 flag[len1] = i;
43 if(s[i]>='a' && s[i]<='z')
44 s1[len1] -= 'a' - 'A';
45 len1++;
46 }
47 for(int i=0; i<len1; i++)
48 s2[i] = s1[len1 - i - 1];
49 s1[len1] = '