题目链接：http://poj.org/problem?id=3096
做完看讨论区，为啥说是STL的题，可能是我太水了。。
思路：
存储所有字母的位置，然后做差分序列，如果有两个差分值相等，那么认为 NOT surprising
#include <stdio.h> using namespace std; //POJ 3096 const int MAXN = 80; int main() { int s[MAXN][MAXN], length[MAXN], line = 0; bool stop = false; while (true) { char c; for (int i = 0; i < MAXN; ++i) { scanf("%c", &c); if (c != '\n'&&c != '*') s[line][i] = int(c - 'A'); if (c == '\n') { length[line] = i; break; } if (c == '*') { stop = true; break; } } if (stop)break; line++; } bool *surprising = new bool[line]; for (int j = 0; j < line; ++j) surprising[j] = true; for (int i = 0; i < line; ++i) { //统计这个字母的的差分序列 int len = length[i]; int *word_pos[26]; int word_len[26]; bool *diff = new bool[len]; for (int j = 0; j < 26; ++j) { word_pos[j] = new int[len]; word_len[j] = 0; } for (int j = 0; j < len; ++j) diff[j] = false; // bool _continue = true; for (int j = 0; j < len; ++j) { int word = s[i][j]; word_pos[word][word_len[word]] = j; word_len[word]++; if (word_len[word] == 1)continue; //统计相同字母的差分 int k = word_len[word] - 1; for (int m = 0; m < k; ++m) { int d = word_pos[word][k] - word_pos[word][m]; if (diff[d]) { surprising[i] = false; _continue = false; break; } if (!_continue)break; if (!diff[d])diff[d] = true; } if (!_continue)break; } delete[] diff; for (int j = 0; j < 26; ++j) delete[] word_pos[j]; } //output for (int i = 0; i < line; ++i) { int len = length[i]; for (int j = 0; j < len; ++j) printf("%c", char(s[i][j] + 65)); if (surprising[i])printf(" is surprising.\n"); else printf(" is NOT surprising.\n"); } return 0; }
