1027: 教你前缀

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 29  

Solved: 6

[ ][ ][ ]

Description

什么是前缀你懂吧，不懂？那我告诉你，假如串S1和S2长度分别是len1，len2，len1<=len2且S2的前len1个字母和S1一样，则S1是S2的前缀。CJR不是在给叶老师做项目嘛，今天遇到一个小问题，找到wuyu，wuyu也不会做，那就请教你来了。叶老师给他很多全是英文小写字母字符串，要她统计一下这里面有多少个串可以做其他串的前缀，重复的串只统计一次。

Input

正整数n，（n<=40000），然后输入n个字符串，每个字符串长度不超过10个字符。

Output

一行，表示这些串里面能做其他串前缀的串的个数。

Sample Input

6 ababa aba bab ab b ab 2 abc abc

Sample Output

3 1

思路：节点除了一般内容外，存储这个节点是否有子节点，也就是当给它增加子节点时修改该节点布尔值；另外存储以该节点为终点的单词数量。最后扫描所有节点，统计其有子节点并且以该节点为终点的单词书不为0，或者该节点为2个以上单词的终点节点个数即可。

#include
      
       #include
       
        using namespace std;int cnt;struct node{    char x;    int c[26],n;    bool s;    void nod1(){memset(c,-1,sizeof(c));n=0;s=false;}}t[130000]; void insert(char s[12]){    int now=s[0]-'a',len=strlen(s),i;    for(i=1;i
        
         1) ans++;        printf("%d\n",ans);    }    return 0;}