Posted on 2009-03-31 13:43
superman 閱讀(150)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("prefix.in", "r", stdin);
8 freopen("prefix.out", "w", stdout);
9
10 string word[202];
11 string s;
12 int n;
13
14 //----read----
15 for (n = 0; true; n++)
16 {
17 cin >> word[n];
18 if (word[n] == ".")
19 break;
20 }
21 while(true)
22 {
23 string ts;
24 if (cin >> ts)
25 s += ts;
26 else
27 break;
28 }
29
30 //----init----
31 sort(word, word + n);
32
33 //----slove----
34 bool x[200002] = { false };
35
36 for (int i = 0; i < n; i++)
37 if (s.substr(0, word[i].size()) == word[i])
38 x[word[i].size() - 1] = true;
39
40 for (int i = 1; i < s.size(); i++)
41 if (x[i - 1] == true)
42 for (int j = 0; j < n; j++)
43 {
44 if (s[i] > word[j][0])
45 continue;
46 if (s[i] < word[j][0])
47 break;
48
49 int k;
50 for (k = 0; k < word[j].size(); k++)
51 if (s[i + k] != word[j][k])
52 break;
53 if (k == word[j].size())
54 x[i + word[j].size() - 1] = true;
55 }
56
57 //----output ans----
58 int ans = 0;
59 for (int i = s.size() - 1; i >= 0; i--)
60 if (x[i])
61 {
62 ans = i;
63 break;
64 }
65
66 if (ans == 0)
67 cout << 0 << endl;
68 else
69 cout << ans + 1 << endl;
70
71 return 0;
72 }
73