寒假第八次训练-字符串

A - 最小表示法

题目大意：给一堆字符串，针对每个字符串问字典序最小的一种串（和圆圈一样任意起点）的首字母序号。

解题思路：朴素算法的话复杂度很高，用最小表示法，若a[i]>a[j]则将i移动至更小的字母处，小于则不处理，相等的话直到a[i+k]!=a[j+k],若a[i+k]>a[j+k]则i=i+k+1,否则j=j+k+1。

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <sstream>
using namespace std;
#define MAXN 10005
char s[MAXN];
int mp(char *s)
{
    int i=0,j=1,k=0,l=strlen(s),t;
    while (i<l && j<l && k<l)
    {
       t=s[(i+k)%l]-s[(j+k)%l];
       if (!t) k++;
       else
       {
           if (t>0) i=i+k+1;
           else j=j+k+1;
           if (i==j) j++;
           k=0;
       }
    }
    return min(i,j);
}
int main()
{
    int i,t;
    //FILE *fp;
    //fp=fopen("output.txt","w");
    scanf("%d",&t);
    while (t--)
    {
        scanf("%s",s);
        printf("%d\n",mp(s)+1);
    }
    //fclose(fp);
}

B - KMP

题目大意：给字符串A，B，问在B中匹配了多少次A。

解题思路：裸KMP

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <sstream>
using namespace std;
#define MAXN 10005
char s[10005],raw[1000005];
int Next[10010];
void get_Next()
{
    int i,j,l=strlen(s);
    Next[0]=Next[1]=0;
    for (i=1; i<=l; i++)
    {
        int j=Next[i];
        while (j && s[i]!=s[j]) j=Next[j];
        Next[i+1]=s[i]==s[j]?j+1:0;
    }
}
int KMP()
{
    int i,l2=strlen(raw),l1=strlen(s),cnt=0,j=0;
    for (i=0;i<l2;i++)
    {
        while(j && s[j]!=raw[i]) j=Next[j];
        if (s[j]==raw[i]) j++;
        if (j==l1) cnt++;
    }
    return cnt;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%s",s);
        scanf("%s",raw);
        get_Next();
        //for (int i=1;i<=strlen(s);i++) printf("%d ",Next[i]);
        printf("%d\n",KMP());
    }
}

D - 字典树

题目大意：给一堆单词和一堆前缀，针对每个前缀，问以该前缀为前缀的单词有多少

解题思路：裸字典树，每个节点计数。应为空间足够所以没有释放空间。

AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <sstream>
using namespace std;
#define MAXN 1024+10
char s[15];
int cnt;
struct tree
{
    tree *next[26];
    int v;
};
tree *root;
void create_tree(char *s)
{
    int l=strlen(s),i;
    tree *p=root;
    for (i=0; i<l; i++)
    {
        int id=s[i]-'a';
        if (p->next[id]==NULL)
        {
            tree *q=new tree;
            for (int j=0; j<26; j++) q->next[j]=NULL;
            p->next[id]=q;
            q->v=1;
            p=q;
        }
        else {p->next[id]->v++;p=p->next[id];}
    }
}
void find_prefix(char *s)
{
    int l=strlen(s);
    tree *p=root;
    for (int i=0;i<l;i++)
    {
        int id=s[i]-'a';
        p=p->next[id];
        if (p==NULL) {cnt=0;return;}
        if (p->v) cnt=p->v;
    }
}
int main()
{
    root=new tree;
    for (int j=0; j<26; j++) {root->next[j]=NULL;}
    root->v=0;
    while (cin.getline(s,15),strlen(s))
    {
        create_tree(s);
    }
    while (~scanf("%s",s))
    {
        cnt=0;
        find_prefix(s);
        printf("%d\n",cnt);
    }
}