<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
西瓜在写编译原理作业中的文法分析器的时候，通常需要检测一个单词是否在给定的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：  
- 根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；  
- 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；  
- 在满足上述条件下，该单词查找树的节点数最少。  
例：图一的单词列表对应图二的单词查找树  
<p><div class='image'><a href='//static.oyohyee.com/post/aoj842.jpg' target='_blank' rel='noopener noreferrer'><img src="//static.oyohyee.com/post/aoj842.jpg" /></a></div></p>
<p>对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>输入一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字符组成，长度不超过63个字符，单词个数不超过5000。</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>输出仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。</p>
<p>{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}</p>
<p>A<br>
AN<br>
ASP<br>
AS<br>
ASC<br>
ASCII<br>
BAS<br>
BASIC</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>13</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>首先对所有字符串进行 <strong>排序</strong> <br>
<img src='//static.oyohyee.com/post/aoj842_2.jpg' height=10% width=10% align='right' /></p>
<p>按照要求把可以合并的圈在一起,可以发现,我们要找的就是<strong>每一个字符串与前一个不同的字符及其后面所有的字符数量和加上1</strong><br>
这一切基于字典序天然的优势(先比较字符再比较大小)</p>
<p>然后计数即可</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp 西瓜的编译原理 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
<p>const int maxn = 5005;<br>
string s[maxn];</p>
<p>int main(){<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>int n = 0;
while(cin &gt;&gt; s[n++]);
sort(s,s+n);

int ans = s[0].size();
for(int i=1;i&lt;n;i++){
    int sz = s[i].size();
    for(int j=0;j&lt;sz;j++){
        if(s[i-1][j] != s[i][j]){
            ans+=sz-j;
            break;
        }
    }
}
cout &lt;&lt; ans+1 &lt;&lt; endl;


#ifdef debug
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;</pre>

AOJ 842.西瓜的编译原理