字符串专题

71 阅读 0 评论 47 点赞

我是靠谱客的博主繁荣秀发，最近开发中收集的这篇文章主要介绍字符串专题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

memory limit exceed:超出内存限制: 一般是①数组开太大②每一组的样例的初始化没初始化好。

1.使用C语言提供的函数：toupper(),tolower()

使用这两个函数需要引入头文件：#include<ctype.h>

ASCII: A~Z:65~90,a~z:97~122

注意调用transfrom时要用头文件#include<algorithm>

string 类大写转小写：

 transform(strA.begin(), strA.end(), strA.begin(), ::tolower);

string类小写转大写：

  transform(strA.begin(), strA.end(), strA.begin(), ::toupper);

1、strcmp(str1,str2):

如果返回值 < 0，则表示 str1 小于 str2。

如果返回值 > 0，则表示 str2 小于 str1。

如果返回值 = 0，则表示 str1 等于 str2。

#include<algorithm>//STL reverse函数的头文件，reverse反转函数，

find()函数

string st2("aabcbcabcbabcc");
    string str1("abc");
    cout << st2.find(str1, 2) << endl;//6   从st2的位置2（b）开始匹配，返回第一次成功匹配时匹配的串（abc）的首字符在st2中的位置，失败返回npos

stringstream类：#include<sstream>，运用此方法不需要讲一群数字组成的串用空格分开

样例①


#include <iostream>
#include <sstream>
#include <string>
#include <set>
using namespace std;
int main(){
	set<string>st;
	string str;
	while(getline(cin,str)){
		st.clear();
		if(str[0]=='#')
			break;
		stringstream strm(str);
		string tmp;
		while(strm>>tmp)
		st.insert(tmp);
		 cout<<st.size()<<endl;
	}
	return 0;
}

样例2：

#include<sstream>
#include<string>
#include<iostream>
using namespace std;
int main(){
    string line;
    while(getline(cin,line)){
        int x;
        stringstream ss(line);  //建立stringstream对象，初始化流内容为line所代表的字符串
        while(ss>>x)            //从line中一次读取数字存入x
        cout<<x<<endl;
    }
    return 0;
}
如果输为："12 23 43 555"
 
则输出为 
12
23
43
555

strtok()

①分解字符串为一组字符串。s为要分解的字符，delim为分隔符字符（如果传入字符串，则传入的字符串中每个字符均为分割符）。首次调用时，s指向要分解的字符串，之后再次调用要把s设成NULL。

②看上面的文字叙述应该不好懂，看下面这段代码就懂了

char s[1000],a[1000][1000];

int main()
{
    while(gets(s))
    {
        if(strcmp(s,"#")==0)
            break;
        int i,j,k,n=0;
        char *p;
        p=strtok(s," ");//以空格分开
        for(i=0;p!=NULL;i++)
        {
            strcpy(a[i],p);
           // cout<<a[i]<<endl;
            p=strtok(NULL," ");
        }
。。。。。。此处省略

2、strncpy():

strncpy 是 C语言的库函数之一，来自 C语言标准库，定义于 string.h，char *strncpy(char *dest, const char *src, int n)，把src所指向的字符串中以src地址开始的前n个字节复制到dest所指的数组中，并返回被复制后的dest。

3、字符串截取：

#include<stdio.h>
#include<string.h>
 
int mid(char str[],int start,int len,char strback[]);
 
int main()
{
	//char a[]="I have a dream";//初始化字符数组就不用指定它的大小
	char str[100];
	char newstr[100];//只是纯粹的申明一个字符数组变量就必须要指定一个大小
	
	gets(str);//在VS2008里面会出现警告(gets不安全。)，把gets改为gets_s就不会出现警告提示了
 
 
	int m=mid(str,2,4,newstr);
	if(m)
	{
		printf("%sn",newstr);//输出字符串，与下面的一样的效果
		//puts(newstr);
	}
	else
	{
		printf("超出字符串长度n");//加上/n才会换行
		puts("超出字符串长度");//输出玩字符串后会自动换行
	}
	return 0;
}
int mid(char str[],int start,int len,char strback[])
{
	int l,i,k=0;
	l=strlen(str);
	if(start+len>l)
		return 0;
	for(i=start;i<start+len;i++)
	{
		strback[k]=str[i];
		k++;
	}
	strback[k]='';//关键一步
	return 1;

}

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher

kmp算法详解，next数组等等，讲的超级好

扩展KMP：具体意思我还不懂啊啊啊啊还是很难的啊扩展kmp算法的详解，这是我唯一看懂的一个详解

const int maxn=100010;   //字符串长度最大值
int next[maxn],ex[maxn]; //ex数组即为extend数组
/*
extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。
*/
 
/*
设辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度
*/
 
//预处理计算next数组
void GETNEXT(char *str)
{
    int i=0,j,po,len=strlen(str);
    next[0]=len;//初始化next[0]
    /*
    0到n-1组成的字符串和str的最长公共前缀长度当然是len了
    */
    while(str[i]==str[i+1]&&i+1<len)//计算next[1]，也就是第一位的时候能匹配多少
    i++;
    next[1]=i;

    po=1;//初始化po的位置
    for(i=2;i<len;i++)
    {
        if(next[i-po]+i<next[po]+po)//第一种情况，可以直接得到next[i]的值
        /*
        如果不如之前计算过的最长的长就直接赋值为最长的那个
        */
        next[i]=next[i-po];
        else//第二种情况，要继续匹配才能得到next[i]的值
        /*
        比最长的还短，那么后面的就不是到了，所以要继续匹配
        */
        {
            j=next[po]+po-i;
            if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配
            while(i+j<len&&str[j]==str[j+i])//计算next[i]
            j++;
            next[i]=j;
            po=i;//更新po的位置
        }
    }
}
//计算extend数组
void EXKMP(char *s1,char *s2)
{
    int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    GETNEXT(s2);//计算子串的next数组
    while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
    i++;
    ex[0]=i;
    po=0;//初始化po的位置
    for(i=1;i<len;i++)
    {
        if(next[i-po]+i<ex[po]+po)//第一种情况，直接可以得到ex[i]的值
        ex[i]=next[i-po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j=ex[po]+po-i;
            if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配
            while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i]
            j++;
            ex[i]=j;
            po=i;//更新po的位置
        }
    }
}

4、kmp中的next数组求最小循环节的应用

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000005;
int next1[maxn];
void getnext(char *s)
{
    int mp=strlen(s);
    int j=0,k=-1;
    next1[0]=-1;
    while(j<mp)
    {
        if(k==-1||s[j]==s[k])
            next1[++j]=++k;
        else
            k=next1[k];
    }
}
char s[maxn];
int main()
{
    while(gets(s))
    {
        if(strcmp(s,".")==0)
            break;
        else
        {
            getnext(s);
            int mp=strlen(s);
            int ans=1;
            if(mp%(mp-next1[mp])==0)
                ans=mp/(mp-next1[mp]);
            cout<<ans<<endl;
        }
    }
    
        
}

求周期性前缀HDU1358

Sample Input
3
aaa
12
aabaabaabaab
0
Sample Output
Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4
for(int i=0; i<=n; i++)
    {
        if(next[i]==-1 || next[i]==0)   //next[i]是-1或0的忽略，说明之前没有周期性前缀
            continue;
        j = i - next[i];
        if(i%j==0)  //能整除，说明存在周期性前缀
            printf("%d %dn",i,i/j);    //输出这个前缀的长度和周期数
    }

manacher的用法详解，讲的很清楚

HDU3068求最长回文串——用manacher法

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<string.h>
#define min(a,b) a<b?a:b
char str[220005],s[220005];
int len,p[220005];

void solve()
{
    int i,mx ,id;
     mx=0;
    for( i=1;s[i]!='';i++)
    {
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])
            p[i]++;
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
    }
}
void init()
{
    s[0]='$';
    s[1]='#';
    int i;
    for(i=0;i<len;i++)
    {
        s[i*2+2]=str[i];
        s[i*2+3]='#';
    }
    len=len*2+2;
    s[len]='#';
}
int main()
{
    int i;
    while(scanf("%s",str)!=EOF)
    {
         len=strlen(str);
        init();
        solve();
        int ans=0;


        for( i=1;i<len;i++)
        {
            if(ans<p[i])
            {
                ans=p[i];
            }
        }
        printf("%dn",ans-1);
    }

    return 0;
}

HDU1238substrings

这个找字串的问题，题目大概意思就是找出所有字符串中共同拥有的一个子串，

该子串（正、逆字符）是任何一个母串的子串，求该子串的最长长度。

方法：首先找到最短的那个字符串，然后对它进行反转，再从大到小的长度对其余输入的字符串进行查找，for循环写的很巧妙

/*Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2*/
#include <iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        string s[maxn];
        int len=105;
        int pos=0;
      int  ma=0;
        for(int i=0; i<n; i++)
        {
            cin>>s[i];
            if(len>s[i].length())
            {
                len=s[i].length();
                pos=i;
            }

        }

        for(int i=s[pos].length(); i>=0; i--)
        {
            for(int j=0; j<s[pos].length()-i+1; j++)
            {
                string s1,s2;
                s1=s[pos].substr(j,i);
                s2=s1;
                reverse(s2.begin(),s2.end());
                int t;
                for( t=0; t<n; t++)
                {
                    if(s[t].find(s1,0)==-1&&s[t].find(s2,0)==-1)
                        break;
                }
                if(t==n&&ma<s1.length())
                    ma=s1.length();
            }
        }
        cout<<ma<<endl;



    }
    return 0;
}

字典树详解

统计问题：https://vjudge.net/problem/HDU-1251

代码如下：注意不要用G++交，C++可以

#include <iostream>
#include<string>
using namespace std;
struct trienode
{
    int countt;//统计单词前缀出现的次数
    trienode* nextt[26];//指向各子树的指针
    bool exist;//标记该结点处是否构成单词
    trienode():countt(0),exist(false)
    {
        for(int i=0;i<26;i++)
        {
            nextt[i]=NULL;
        }
    }
};
void trieinsert(trienode* root,string &word)
{
    trienode *node=root;
    int id;
    int len=word.size();
    int i=0;
    while(i<len)
    {
        id=word[i]-'a';
        if(node->nextt[id]==NULL)
            node->nextt[id]=new trienode();
        node=node->nextt[id];
        node->countt+=1;
        i++;
    }
    node->exist=true;//单词结束，可以构成一个单词
}
int triesearch(trienode* root,string &word)
{
    trienode *node=root;
    int len=word.size();
    int i=0;
    while(i<len)
    {
        int id=word[i]-'a';
        if(node->nextt[id]!=NULL)
        {
            node=node->nextt[id];
            i++;
        }
        else
            return 0;
    }
    return node->countt;
}
int main()
{
    trienode *root=new trienode();
   // int flag=false;
    string word;
    while(getline(cin,word)&&word.compare("")!=0)
    {
        trieinsert(root,word);
    }
    while(cin>>word)
        cout<<triesearch(root,word)<<endl;
    return 0;
}

例题：

给你一堆英文单词（可能有4000000个。用普通查询铁定让你TLE）。找出出现次数最多的，输出这个单词，并输出出现的次数。

思路：

如果数据范围很小，我们可以用STL里面的map映射来做，但是数据范围太大，用普通的数据结构肯定会超时，所以要考虑更优的数据结构。当然，这题也是赤裸裸的字典树应用。当然，也可以用hash来做。

#include<iostream>
#include<algorithm>
using namespace std;
struct Dictree
{
   int count;//单词出现的次数
   struct Dictree *tire[26];//26个子节点
}*a;
void init()
{
   a = new Dictree;
   for(int i = 0;i < 26;i++)
	   a->tire[i] = NULL;//子节点指针置空
}
int insert(char str[])
{
   int len ,res;
   Dictree *head = a;//head是头指针，每次变化。但a不变，每次从头指针开始
   len = strlen(str);
   for(int i = 0;i < len;i++)
   {
       res = (int) (str[i] - 97);//下标对应字母
	   if(head->tire[res] == NULL)//没有此字母，开始新节点并初始化
	   {
	      head->tire[res] = new Dictree;
		  head = head->tire[res];//和下一个顺序不能反，先指向开辟节点，再赋值为0
		  head->count = 0;
		  for(int j = 0;j < 26;j++)
		  {
		     head->tire[j] = NULL;
		  }
	   }
	   else head = head->tire[res];
   }
   head->count++;//记录单词出现次数
   return head->count;//返回单词出现的次数
 
}
int main()
{
  int num, tmp,maxlen = 0;
  char ani[11],ans[11];
  init();
  cin>>num;
  for(int i = 0;i < num;i++)
  {
     cin>>ani;
	 tmp = insert(ani);
	 if(tmp > maxlen)
	 {
	   maxlen = tmp;
	   strcpy(ans,ani);
	 }
  }
  cout<<ans<<" "<<maxlen<<endl;
  return 0;

}

但数据较少，也可以用map

#include<map>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
 
 
int main()
{
	int n;
	char animal[11];
	map<string, int> ani;
	map<string, int>::iterator pos, num;
	cin>>n;
	for(int i = 0; i < n; ++i)
	{
		cin>>animal;
		ani[animal] += 1;
	}
	for(pos = ani.begin(), num = ani.begin(); pos != ani.end(); ++pos)
	{
		if(pos->second > num->second)
		{
			num = pos;
		}
	}
	cout<<num->first<<" "<<num->second<<endl;
	return 0;

}

字典树练习

练习

hdu 2072 单词数

解题思路：http://blog.csdn.net/piaocoder/article/details/41902793

hdu 1671 Phone List

解题思路：http://blog.csdn.net/piaocoder/article/details/47951011

POJ 2001 Shortest Prefixes

解题思路：http://blog.csdn.net/piaocoder/article/details/47731321

POJ 2418 Hardwood Species

解题思路：http://blog.csdn.net/piaocoder/article/details/47731453

POJ 2503 Babelfish

解题思路：http://blog.csdn.net/piaocoder/article/details/47731701

1、问题 A: 求最长公共子串（串）

题目描述

求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。

输入

输入两个字符串

输出

输出公共子串

样例输入

abcdef

adbcef

样例输出 bc

这个方法好理解，不知道效率怎么样

#include<iostream>
#include<algorithm>
#include <vector>
#include<cstring>
//#include<string.h>
#include<ctype.h>
//#include<math.h>
//#include<stdlib.h>
//#include<stdio.h>
using namespace std;
void fun();
int main()
{
	fun();
	return 0;
}
void fun()
{
	char str0[100],str1[100],dest[100];
	//gets(str0);
	cin>>str0;
	cin>>str1;
	//gets(str1);
	if(!strcmp(str0,str1))
		//puts(str1);
		cout<<str1<<endl;
	else
	{
		memset(dest,'',sizeof(dest));
		int i,j,n,length=0,end=0,arr[100][100];
		for(i=0;str0[i];i++)
		{
			for(j=0;str1[j];j++)
			{
				n = (i - 1 >= 0 && j - 1 >= 0) ? arr[i - 1][ j - 1] : 0;
				arr[i][j] = str0[i] == str1[j] ? 1 + n : 0;
				if (arr[i][j] > length)
				{
					length = arr[i][j];
					end = i;
				}
			}
		}
		if(length==0)
			cout<<"false"<<endl;
		else
		{
			strncpy(dest,&str0[end - length + 1],length);
			cout<<dest<<endl;
		}
	}
}

2、KMP模板题：判断pattern是否是text的子串，并返回匹配的第一个位置

/*Sample Input
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
Sample Output
6
-1*/
//All integers are in the range of [-1000000, 1000000].
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000005;
int next1[maxn];
int text[maxn],pattern[maxn];
int ans;
void getnext(int s[],int len)
{
    int j=-1;
    next1[0]=-1;
    for(int i=1;i<len;i++)
    {

        while(j!=-1&&s[i]!=s[j+1])
            j=next1[j];//不断执行此循环，知道j回退到-1，或是s[i]==s[j+1]
        if(s[i]==s[j+1])
            j++;
        next1[i]=j;
    }
}
//kmp算法，判断pattern是否是text的子串
bool kmp(int text1[],int pattern1[],int n,int m)
{
   // int n=strlen(text),m=strlen(pattern);
    getnext(pattern1,m);//计算pattern的子串
    int j=-1;//初始化为-1，表示当前还没有一位被匹配

    for(int i=0;i<n;i++)
    {
        while(j!=-1&&text1[i]!=pattern1[j+1])
        {
            j=next1[j];
        }

        if(text1[i]==pattern1[j+1])//当第一次执行该循环？不是这样的，后面可能不匹配
        {
            ans=i;
            j++;
        }


        if(j==m-1)
            return true;


    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    int m,n;

    while(T--)
    {

       scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%d",&text[i]);
        for(int i=0;i<m;i++)
           scanf("%d",&pattern[i]);
        if(kmp(text,pattern,n,m))
            cout<<ans-m+2<<endl;//ans-m+2代表成功匹配的初始位置

        else
             cout<<"-1"<<endl;
        ans=0;

    }

    return 0;
}

3、如果是HDU2087（剪花布）这种题，应该在每次匹配成功后把j移动到0的位置

AC自动机

hdu2222 http://acm.hdu.edu.cn/showproblem.php?pid=2222

#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int cnt;//是否为该单词的最后一个节点
    node *fail;//失败指针
    node *nextt[130];
    node()
    {
        cnt=0;
        fail=0;
        memset(nextt,NULL,sizeof(nextt));
    }
};//队列，方便用BFS构造失败指针
char s[1000005];//主字符串
char keyword[55];//需要查找的单词
int head,tail;
node *root;//头节点
/*void init(node *root)
{
    root->cnt=0;
    root->fail=NULL;
    for(int i=0;i<130;i++)
        root->nextt[i]=NULL;
}*/
void build_trie(char *keyword)
{
   // node *p,*q;
   node *p=root;
    int i,v;
    int len=strlen(keyword);
    for(i=0;i<len;i++)
    {
       // v=keyword[i]-'a';
       v=keyword[i];//注意这里，想要这样用的话，把nextt数组开大一点即可，例如130
        if(p->nextt[v]==NULL)
        {
            //q=(struct ndoe*)malloc(sizeof(node));

           // q=(struct node*)malloc(sizeof(node));
           // q=new node;
            //init(q);
            p->nextt[v]=new node();//节点链接
        }
        p=p->nextt[v];
    }
    p->cnt++;//单词最后一个节点cnt++,代表一个单词
}
void build_ac_fail(node *root)
{
    queue <node *> que;
    root->fail=NULL;
    que.push(root);
    while(!que.empty())
    {
        node *temp=que.front();
        que.pop();
        node *p=NULL;
        for(int i=0; i<130; i++)
        {
            if(temp->nextt[i]!=NULL)
            {
                if(temp==root) temp->nextt[i]->fail=root;
                else
                {
                    p=temp->fail;
                    while(p!=NULL)
                    {
                        if(p->nextt[i]!=NULL)
                        {
                            temp->nextt[i]->fail=p->nextt[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL)
                        temp->nextt[i]->fail=root;
                }
                que.push(temp->nextt[i]);
            }
        }
    }


}
/*void build_ac_fail(node *root)
{
    head=0,tail=0;//队列头、尾指针
    queuet[head++]=root;//先将root入队
    while(head!=tail)
    {
        node *p=NULL;
        node *temp=queuet[tail++];//弹出队头结点
        for(int i=0;i<130;i++)
        {
            if(temp->nextt[i]!=NULL)//找到实际存在的字符节点
            {
                //temp->nextt[i] 为该节点，temp为其父节点
                if(temp==root)//若是第一层中的字符节点，则把该节点指针指向root
                    temp->nextt[i]->fail=root;
                else
                    {
                        //依次回溯该节点的父节点的失败指针直到某节点的nextt[i]与该节点相同
                        //则把该节点的失败指针指向该nextt[i]节点
                        //若回溯到root都没有找到，则该节点的失败指针指向root
                        p=temp->fail;//把该节点的父节点的失败指针给p
                        while(p!=NULL)
                        {
                            if(p->nextt[i]!=NULL)
                            {
                                temp->nextt[i]->fail=p->nextt[i];
                                break;
                            }
                            p=p->fail;
                        }
                        //让该节点的失败指针也指向root
                        if(p==NULL)
                            temp->nextt[i]->fail=root;
                    }
                    queuet[head++]=temp->nextt[i];//每处理一个节点，都让该节点依次入队

            }
        }
    }
*/
int query(node *root)//匹配
{
    //i为主串指针，p为模式串指针
    int i,v,countt=0;
    node *p=root;
    int len=strlen(s);
    for(i=0;i<len;i++)
    {
       // v=s[i]-'a';
       v=s[i];
        //由失败指针回溯查找，判断s[i]是否存在于trie树中
        while(p->nextt[v]==NULL&&p!=root)
            p=p->fail;
        p=p->nextt[v];//找到后p指针指向该节点
        if(p==NULL)//若指针返回为空，则没有找到与之匹配的字符
            p=root;
        node *temp=p;//匹配该节点后，沿其失败指针回溯，判断其它节点是否匹配
        while(temp!=root)//匹配结束控制
        {
            if(temp->cnt>=0)//判断该节点是否被访问
            {
                countt+=temp->cnt;//由于cnt初始化为0，所以cnt>0时才统计了单词的个数
                temp->cnt=-1;//标记已访问过
            }
            else//节点已经访问，退出循环
                break;
            temp=temp->fail;//回溯，失败指针，继续寻找下一个节点
        }
    }
    return countt;
}
int main()
{
   int T,n;
   cin>>T;
   while(T--)
   {
       /*root=(struct node*)malloc(sizeof(node));
       init(root);*/
       root=new node();
       cin>>n;
       for(int i=0;i<n;i++)
       {
           scanf("n%s",keyword);
           build_trie(keyword);
       }
       build_ac_fail(root);
       scanf("n%s",s);
       printf("%dn",query(root));
   }
    return 0;
}

#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node
{
    int cnt;//是否为该单词的最后一个节点
    node *fail;//失败指针
    node *nextt[130];
}*queuet[500005];//队列，方便用BFS构造失败指针
char s[1000005];//主字符串
char keyword[55];//需要查找的单词
int head,tail;
node *root;//头节点
void init(node *root)
{
    root->cnt=0;
    root->fail=NULL;
    for(int i=0;i<130;i++)
        root->nextt[i]=NULL;
}
void build_trie(char *keyword)
{
    node *p,*q;
    int i,v;
    int len=strlen(keyword);
    for(i=0,p=root;i<len;i++)
    {
       // v=keyword[i]-'a';
       v=keyword[i];//注意这里，想要这样用的话，把nextt数组开大一点即可，例如130
        if(p->nextt[v]==NULL)
        {
            //q=(struct ndoe*)malloc(sizeof(node));

            q=(struct node*)malloc(sizeof(node));
           // q=new node;
            init(q);
            p->nextt[v]=q;//节点链接
        }
        p=p->nextt[v];
    }
    p->cnt++;//单词最后一个节点cnt++,代表一个单词
}
void build_ac_fail(node *root)
{
    head=0,tail=0;//队列头、尾指针
    queuet[head++]=root;//先将root入队
    while(head!=tail)
    {
        node *p=NULL;
        node *temp=queuet[tail++];//弹出队头结点
        for(int i=0;i<130;i++)
        {
            if(temp->nextt[i]!=NULL)//找到实际存在的字符节点
            {
                //temp->nextt[i] 为该节点，temp为其父节点
                if(temp==root)//若是第一层中的字符节点，则把该节点指针指向root
                    temp->nextt[i]->fail=root;
                else
                    {
                        //依次回溯该节点的父节点的失败指针直到某节点的nextt[i]与该节点相同
                        //则把该节点的失败指针指向该nextt[i]节点
                        //若回溯到root都没有找到，则该节点的失败指针指向root
                        p=temp->fail;//把该节点的父节点的失败指针给p
                        while(p!=NULL)
                        {
                            if(p->nextt[i]!=NULL)
                            {
                                temp->nextt[i]->fail=p->nextt[i];
                                break;
                            }
                            p=p->fail;
                        }
                        //让该节点的失败指针也指向root
                        if(p==NULL)
                            temp->nextt[i]->fail=root;
                    }
                    queuet[head++]=temp->nextt[i];//每处理一个节点，都让该节点依次入队

            }
        }
    }
}
int query(node *root)//匹配
{
    //i为主串指针，p为模式串指针
    int i,v,countt=0;
    node *p=root;
    int len=strlen(s);
    for(i=0;i<len;i++)
    {
       // v=s[i]-'a';
       v=s[i];
        //由失败指针回溯查找，判断s[i]是否存在于trie树中
        while(p->nextt[v]==NULL&&p!=root)
            p=p->fail;
        p=p->nextt[v];//找到后p指针指向该节点
        if(p==NULL)//若指针返回为空，则没有找到与之匹配的字符
            p=root;
        node *temp=p;//匹配该节点后，沿其失败指针回溯，判断其它节点是否匹配
        while(temp!=root)//匹配结束控制
        {
            if(temp->cnt>=0)//判断该节点是否被访问
            {
                countt+=temp->cnt;//由于cnt初始化为0，所以cnt>0时才统计了单词的个数
                temp->cnt=-1;//标记已访问过
            }
            else//节点已经访问，退出循环
                break;
            temp=temp->fail;//回溯，失败指针，继续寻找下一个节点
        }
    }
    return countt;
}
int main()
{
   int T,n;
   cin>>T;
   while(T--)
   {
       root=(struct node*)malloc(sizeof(node));
       init(root);
       cin>>n;
       for(int i=0;i<n;i++)
       {
           scanf("n%s",keyword);
           build_trie(keyword);
       }
       build_ac_fail(root);
       scanf("n%s",s);
       printf("%dn",query(root));
   }
    return 0;
}

hdu2896http://acm.hdu.edu.cn/showproblem.php?pid=2896

/*依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。
web 网站编号: 病毒编号 病毒编号 …
冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。
最后一行输出统计信息，如下格式
total: 带病毒网站数
冒号后有一个空格。
Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
Sample Output
web 1: 1 2 3
total: 1*/
#include <iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=10010;//在hdu2896这道题中，我的初始化出现了问题
struct node
{
    int cnt;//是否为该单词的最后一个节点
    int code;
    node *fail;//失败指针
    node *nextt[130];
    node()
    {
        fail=NULL;
        code=0;
        cnt=0;
        memset(nextt,NULL,sizeof(nextt));
    }

};//队列，方便用BFS构造失败指针

//需要查找的单词

int ans[5];//标记主串中含有病毒的编号

/*void init(node *root)//我用这个函数，提交超内存
{
    root->cnt=0;
    root->code=0;
    root->fail=NULL;
    for(int i=0; i<130; i++)//注意这里是大小写字母均存在，用130 这个范围,以后如果要谜面这种情况，直接用构造函数，sizeof(nextt)
        root->nextt[i]=NULL;
}*/
void build_trie(node*root,char *keyword,int x)
{
    node *p=root;
    int i=0,v;
   int len=strlen(keyword);
   /*while(keyword[i])
    {
          v=keyword[i];
        if(p->nextt[v]==NULL)
        {
           p->nextt[v]=new node();
        }
        p=p->nextt[v];
        i++;
    }*/

   for(i=0,p=root; i<len; i++)
    {
        v=keyword[i];//这个地方很巧妙。可以不用向上次那样keyword[i]-'a'
        if(p->nextt[v]==NULL)
        {
        //q=new node;
          //  init(q);
           // p->nextt[v]=q;
            p->nextt[v]=new node();//节点链接
        }
        p=p->nextt[v];
    }
    p->code=x;
    // p->cnt=1;
    p->cnt++;//单词最后一个节点cnt++,代表一个单词
}
void build_ac_fail(node *root)
{
    queue <node *> que;
    root->fail=NULL;
    que.push(root);
    while(!que.empty())
    {
        node *temp=que.front();
        que.pop();
        node *p=NULL;
        for(int i=0; i<130; i++)
        {
            if(temp->nextt[i]!=NULL)
            {
                if(temp==root) temp->nextt[i]->fail=root;
                else
                {
                    p=temp->fail;
                    while(p!=NULL)
                    {
                        if(p->nextt[i]!=NULL)
                        {
                            temp->nextt[i]->fail=p->nextt[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL)
                        temp->nextt[i]->fail=root;
                }
                que.push(temp->nextt[i]);
            }
        }
    }


}
int query(node *root,char *str)
{
    int i=0,cnnt=0,index;
    node *p=root;
    while(str[i])
    {
        index=str[i];
        while(p->nextt[index]==NULL&&p!=root)
            p=p->fail;
        p=p->nextt[index];
        if(p==NULL) p=root;
        node *temp=p;
        while(temp!=root&&temp->code)
        {
            ans[cnnt]=temp->code;
            cnnt+=p->cnt;
            temp=temp->fail;
        }
        i++;
    }
    return cnnt;
}

int main()
{
    int T;
    char s[maxn];//主字符串
    char keyword[205];
    while(scanf("%d",&T)!=EOF)
    {
       node * root=new node();
       /* node *root=new node;
        init(root);*/
        for(int i=1; i<=T; i++)
        {
            scanf("%s",keyword);

            build_trie(root,keyword,i);
        }
        build_ac_fail(root);
        int sum=0;
        int M;
        scanf("%d",&M);
        for(int i=1; i<=M; i++)
        {
            scanf("%s",s);
            int flag=0;
            int num=query(root,s);
           if(num)
            {
                flag=true;
                printf("web %d:",i);
                sort(ans,ans+num);
                for(int j=0; j<num; j++)
                    printf(" %d",ans[j]);
                printf("n");
            }
            if(flag)
                sum++;
        }
        printf("total: %dn",sum);
    }

    return 0;
}

POj1035 字符串处理

题意：前面是字典，后面是单词表，单词表中的单词通过替换、删除、增加一个字母能否在字典中找到，如果有，则输出

#include <stdio.h>
#include <string.h>
char dic[10005][20];
char wor[55][20];
int di,dj;
int Correct(char *wor)
{
	for(int i=0;i<di;i++)
		if(strcmp(wor,dic[i])==0)
			return 1;
	return 0;
}
int Replace(char *s1,char *s2)
{
	 int mistake=0,i;
	 for(i=0;i<strlen(s1);i++)
	 	if(s1[i]!=s2[i])
	 	{
	 		mistake++;
	 		if(mistake>1)
	 			return 0;
	 	}
	return 1;
}
int Dellet(char *s1,char *s2)
{
	//mistake记录两个单词中对应位置字符不相等的个数 
	int mistake=0,i,j;
	 for(i=0,j=0;i<strlen(s1);)
	 { 
	 	if(s1[i]!=s2[j])
	 	{
	 		mistake++; i++;
	 		if(mistake>1)
	 			return 0;
	 	}
	 	else
	 	{
	 		i++; j++;
	 	}
	 }
	return 1;
}
int main()
{
	di=0; dj=0;
	while(gets(dic[di]) && dic[di][0]!='#')
		di++;
	while(gets(wor[dj]) && wor[dj][0]!='#')
		dj++;
	for(int i=0;i<dj;i++)//需要操作的单词 
	{
		if(Correct(wor[i]))//原单词是否在字典中 
		{
			printf("%s is correctn",wor[i]); continue;
		}
		printf("%s: ",wor[i]);
		for(int j=0;j<di;j++)//字典序列 
		{
			int leni=strlen(wor[i]);//单词 
			int lenj=strlen(dic[j]);//字典 
			if(leni==lenj)
			{//两者长度相等，则只需判断两个单词的每一位
			//是否相等若只有一位不相等，则满足替换 
				if(Replace(wor[i],dic[j]))
					printf("%s ",dic[j]);				
			}
			else if(leni-lenj==1)
			{//单词的长度比字典中的单词大 1，则判断是否能够
			 //通过删除一个字符得到字典中的单词 
				if(Dellet(wor[i],dic[j]))
					printf("%s ",dic[j]);
			}
			else if(leni-lenj==-1)
			{//单词的长度比字典中的单词小 1，则判断是否能够
			 //通过添加一个字符得到字典中的单词，可以通过交换
			 //传的参数仍然用Dellet()函数实现 
				if(Dellet(dic[j],wor[i]))
					printf("%s ",dic[j]);
			}
		}
		printf("n");
	}
	return 0;
}