字符串
最后更新于：2022-04-01 21:46:35
## 字符串
程序1：循环输入并将每个单词插入集合S(忽略重复单词)，然后排序输出。
~~~
int main(void) {
set s;
set::iterator j;
string t;
while(cin >> t)
s.insert(t);
for(j=s.begin(); j!=s.end(); ++j)
cout<<*j< m;
map::iterator j;
string t;
while(cin >> t)
m[t]++;
for(j=m.begin(); j!=m.end(); ++j)
cout<first<<" "<second<next) {
char* dst = (char*)p->word;
int i = 0;
for(; *(str+i) && *(str+i)==*(dst+i); ++i);
if(!*(str+i) && !*(dst+i)) return true;
}
return false;
}
private:
unsigned int hash(const char* str) {// BKDR Hash Function
unsigned int hash = 0;
while(*str) {
hash = hash * seed_ + (*str++);
}
return (hash & 0x7FFFFFFF) % kHashSize;
}
private:
unsigned int seed_;
unsigned int size_;
static const int kWordSize = 26 + 1;
static const int kNodeSize = 20000;
static const int kHashSize = 10001;
struct Node {
char word[kWordSize];
Node *next;
};
Node node_[kNodeSize];
Node* head_[kHashSize];
};
~~~
**后缀数组**
假设我们有以下字符串及一个char*数组：
~~~
char c[20] = "hawstein";
char* pc[20];
~~~
我们让指针pc[i]指向字符串的第i个字符，即：
~~~
for(int i=0; i<8; ++i)
pc[i] = &c[i];
~~~
这时候我们输出pc[i]，会得到字符串"hawstein"的所有后缀：
~~~
hawstein
awstein
wstein
stein
tein
ein
in
n
~~~
然后，我们对数组pc进行排序，将所有后缀按字典序排序：
~~~
sort(pc, pc+8, cmp);
~~~
其中，比较函数cmp如下：
~~~
inline bool cmp(char* p, char*q) {
return strcmp(p, q) < 0;
}
~~~
这时，我们再输出pc[i]，会得到排序后的结果：
~~~
awstein
ein
hawstein
in
n
stein
tein
wstein
~~~
我们把数组pc称为“后缀数组”。这里需要注意，数组pc 中存储的是指向每个后缀首字符的地址。我们也可以存储每个后缀首字符在原数组中的下标， 效果是一样的。
本章中用后缀数组解决了一个小问题：可重叠最长重复子串。比如对于字符串"banana"， 其后缀数组为：
~~~
a
ana
anana
banana
na
nana
~~~
扫描一次数组，比较相邻子串，找到相邻子串的最长公共前缀即可。本例为"ana"， 其中一个a是重叠的。
后缀数组是处理字符串的有力工具，常见的两种实现方法是：倍增算法和DC3算法。 推荐阅读以下材料来学习后缀数组：
> > 许智磊，《后缀数组》
> >
> > 罗穗骞，《后缀数组——处理字符串的有力工具》
';