當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

字符串入门

發布時間：2023/12/10 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了字符串入门小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

暴力

字典樹總結：字典樹的功能就是map字符串得到編碼或者查詢前綴關系套模板的時候注意t,s,－‘a’,[26],sz=0的初始化還有一個問題，到底字典樹開多少內存比較合適，反正至少是要開字符總長度*2 hdu1251? http://acm.hdu.edu.cn/showproblem.php?pid=1251 給定字符串集合S，之后每次詢問一個字符串ch求S中以ch為前綴的字符串數目。字典樹,構造時每一個insert過程中遇到的節點都自增，之后ch每一個直接查詢。就是不知道為什么第47行代碼是必須的。 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<functional> 6 #include<iostream> 7 #include<cmath> 8 #include<cctype> 9 #include<stack> 10 #include<set> 11 #include<map> 12 #include<ctime> 13 using namespace std; 14 #define For(i,n) for(int i=1;i<=n;i++) 15 #define Fork(i,k,n) for(int i=k;i<=n;i++) 16 #define Rep(i,n) for(int i=0;i<n;i++) 17 #define ForD(i,n) for(int i=n;i;i--) 18 #define RepD(i,n) for(int i=n;i>=0;i--) 19 #define Forp(x) for(int p=pre[x];p;p=next[p]) 20 #define Lson (x<<1) 21 #define Rson ((x<<1)+1) 22 #define MEM(a) memset(a,0,sizeof(a)); 23 #define NEG(a) memset(a,-1,sizeof(a)); 24 #define INF 0x3f3f3f3f 25 #define LLINF 0x3f3f3f3f3f3f3f3f 26 #define MAXN 1000000 27 #define ll long long 28 int t[MAXN][26],sz,s[MAXN]; 29 void insert(char ch[]) 30 { 31 int k,len=strlen(ch),now=0; 32 Rep(p,len) 33 { 34 // printf("%c\n",ch[p]); 35 k=ch[p]-'a'; 36 if(t[now][k]==0) t[now][k]=++sz; 37 now=t[now][k]; 38 s[now]++; 39 } 40 } 41 int ask(char ch[]) 42 { 43 int now=0,k,len=strlen(ch); 44 Rep(p,len) 45 { 46 k=ch[p]-'a'; 47 if(t[now][k]==0) return 0; 48 now=t[now][k]; 49 } 50 return s[now]; 51 } 52 int main() 53 { 54 char buf[200]; 55 sz=0; 56 while(true) 57 { 58 gets(buf); 59 if(buf[0]==0) 60 break; 61 insert(buf); 62 } 63 while(scanf("%s",buf)!=EOF) 64 { 65 printf("%d\n",ask(buf)); 66 } 67 68 } View Code

hdu1617

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

給定字符串集合S，問是否有字符串i，j屬于S并且i為j的前綴

字典樹，構造時insert的時候直接返回是否觸犯這個規則，標記兩種，

一種是1，表示這條路曾經有字符串走過，一種是2，表示這個點是一個字符串的結尾，這樣就可以了。

hdu1247

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

稍微開始加難點，給定字符串集合S,問S內是否有兩個單詞構成另外一個單詞?

字典樹，先完成trie，然后再次討論每一個字符串i，若i在ask時遇到一個字符串end標記，

就從這里開始到i結尾作為一個字符串去trie樹中查詢是否存在

1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<functional> 6 #include<iostream> 7 #include<cmath> 8 #include<string> 9 #include<vector> 10 #include<cctype> 11 #include<stack> 12 #include<set> 13 #include<map> 14 #include<ctime> 15 using namespace std; 16 #define For(i,n) for(int i=1;i<=n;i++) 17 #define Fork(i,k,n) for(int i=k;i<=n;i++) 18 #define Rep(i,n) for(int i=0;i<n;i++) 19 #define ForD(i,n) for(int i=n;i;i--) 20 #define RepD(i,n) for(int i=n;i>=0;i--) 21 #define Forp(x) for(int p=pre[x];p;p=next[p]) 22 #define Lson (x<<1) 23 #define Rson ((x<<1)+1) 24 #define MEM(a) memset(a,0,sizeof(a)); 25 #define NEG(a) memset(a,-1,sizeof(a)); 26 #define INF 0x3f3f3f3f 27 #define LLINF 0x3f3f3f3f3f3f3f3f 28 #define MAXN 500000 29 #define ll long long 30 int t[MAXN][26]; 31 int sz,s[MAXN]; 32 void insert(char ch[]) 33 { 34 int k,len=strlen(ch),now=0; 35 Rep(p,len) 36 { 37 k=ch[p]-'0'; 38 if(t[now][k]==0) t[now][k]=++sz; 39 now=t[now][k]; 40 } 41 s[now]=1; 42 } 43 char buf[500000][50]; 44 int nume; 45 vector<string>ans; 46 int get(char ch[]) 47 { 48 int len=strlen(ch),k,now=0; 49 Rep(p,len) 50 { 51 k=ch[p]-'0'; 52 if(t[now][k]==0) return 0; 53 now=t[now][k]; 54 } 55 return s[now]; 56 } 57 void ask(char ch[]) 58 { 59 int len=strlen(ch),k,now=0; 60 Rep(p,len) 61 { 62 k=ch[p]-'0'; 63 if(s[now]==1&&get(ch+p)==1) 64 { 65 string tmp(ch); 66 ans.push_back(tmp); 67 return; 68 } 69 now=t[now][k]; 70 } 71 } 72 int main() 73 { 74 //freopen("in.txt","in",stdin); 75 while(gets(buf[nume])&&buf[nume][0]!=0) 76 { 77 insert(buf[nume]); 78 //printf("buf=%s\n",buf[nume]); 79 nume++; 80 //printf("nume=%d\n",nume); 81 } 82 Rep(i,nume) 83 { 84 //printf("%s\n",buf[i]); 85 ask(buf[i]); 86 } 87 sort(ans.begin(),ans.end()); 88 sz=ans.size(); 89 Rep(i,sz) 90 { 91 cout<<ans[i]<<endl; 92 } 93 return 0; 94 } View Code

hdu4099

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

10w以內的斐波那契數作為集合S，問一個不超過長度40的數字i是否是某一個S內的數字j的前綴，

如果是求符合的j的最小下標

字典樹，insert所有的斐波，但是顯然開不下那么大的，注意到40的范圍，所以insert的時候只留下40長度，

開800w數組。同時為了方便后來的查詢，每當字典樹開新節點的時候標記下標。

1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<functional> 6 #include<iostream> 7 #include<cmath> 8 #include<string> 9 #include<vector> 10 #include<cctype> 11 #include<stack> 12 #include<set> 13 #include<map> 14 #include<ctime> 15 using namespace std; 16 #define For(i,n) for(int i=1;i<=n;i++) 17 #define Fork(i,k,n) for(int i=k;i<=n;i++) 18 #define Rep(i,n) for(int i=0;i<n;i++) 19 #define ForD(i,n) for(int i=n;i;i--) 20 #define RepD(i,n) for(int i=n;i>=0;i--) 21 #define Forp(x) for(int p=pre[x];p;p=next[p]) 22 #define Lson (x<<1) 23 #define Rson ((x<<1)+1) 24 #define MEM(a) memset(a,0,sizeof(a)); 25 #define NEG(a) memset(a,-1,sizeof(a)); 26 #define INF 0x3f3f3f3f 27 #define LLINF 0x3f3f3f3f3f3f3f3f 28 #define MAXN 8000000 29 #define ll long long 30 #define out(name,a) cout<<name<<"="<<a<<endl; 31 int t[MAXN][10]; 32 int sz,s[MAXN],c[100000]; 33 void add(char a[],char b[],char back[])//計算 a+b，結果存入 c, 34 { 35 36 int i,j,k; 37 int x,y,z; 38 int up; 39 i=strlen(a)-1; 40 j=strlen(b)-1; 41 k=0; 42 up=0; 43 while(i>=0||j>=0) 44 { 45 if(i<0)x=0; 46 else x=a[i]-'0'; 47 if(j<0)y=0; 48 else y=b[j]-'0'; 49 z=x+y+up; 50 c[k++]=z%10+'0'; 51 up=z/10; 52 i--; 53 j--; 54 } 55 if(up>0)c[k++]=up+'0'; 56 for(i=0;i<k;i++)back[i]=c[k-1-i]; 57 back[k]='\0'; 58 } 59 void insert(char ch[],int idx) 60 { 61 int k,len=strlen(ch),now=0; 62 len=min(len,41); 63 Rep(p,len) 64 { 65 k=ch[p]-'0'; 66 if(t[now][k]==0) t[now][k]=++sz,s[t[now][k]]=idx; 67 now=t[now][k]; 68 69 } 70 } 71 int ask(char ch[]) 72 { 73 int len=strlen(ch),k,now=0; 74 Rep(p,len) 75 { 76 k=ch[p]-'0'; 77 if(t[now][k]==0) return -1; 78 now=t[now][k]; 79 } 80 return s[now]; 81 } 82 char now[100],pre[100],buf[100]; 83 void init() 84 { 85 NEG(s); 86 now[0]='1';now[1]=0; 87 pre[0]='1';pre[1]=0; 88 insert(now,0); 89 Fork(i,2,99999) 90 { 91 add(now,pre,buf); 92 strcpy(pre,now); 93 strcpy(now,buf); 94 int len1=strlen(pre),len2=strlen(now); 95 if(len2>60) pre[len1-1]=0,now[len2-1]=0; 96 insert(now,i); 97 } 98 } 99 int main() 100 { 101 int T; 102 scanf("%d",&T); 103 init(); 104 For(kases,T) 105 { 106 scanf("%s",buf); 107 printf("Case #%d: %d\n",kases,ask(buf)); 108 } 109 return 0; 110 } View Code

poj1056

http://poj.org/problem?id=1056

和hdu1617完全一模一樣

poj2513? http://poj.org/problem?id=2513 題意理解錯誤，要求的是所有的木棒連接，連接條件是連接處同色。顏色顯然要hash成編碼，所以會有兩種思路，本質相同，一種map，一種是trie樹進行編碼，每次用的時候查詢編碼過沒有。之后是解決所有木棒連接回路，那么就是歐拉回路，連通性要用到并查集。還犯了一個錯誤就是套模板的時候數字trie樹是-'0'的字母trie樹是-'a'的 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<functional> 6 #include<iostream> 7 #include<cmath> 8 #include<string> 9 #include<cctype> 10 #include<stack> 11 #include<set> 12 #include<map> 13 #include<ctime> 14 using namespace std; 15 #define For(i,n) for(int i=1;i<=n;i++) 16 #define Fork(i,k,n) for(int i=k;i<=n;i++) 17 #define Rep(i,n) for(int i=0;i<n;i++) 18 #define ForD(i,n) for(int i=n;i;i--) 19 #define RepD(i,n) for(int i=n;i>=0;i--) 20 #define Forp(x) for(int p=pre[x];p;p=next[p]) 21 #define Lson (x<<1) 22 #define Rson ((x<<1)+1) 23 #define MEM(a) memset(a,0,sizeof(a)); 24 #define NEG(a) memset(a,-1,sizeof(a)); 25 #define INF 0x3f3f3f3f 26 #define LLINF 0x3f3f3f3f3f3f3f3f 27 #define MAXN 1000000 28 #define ll long long 29 int t[MAXN][26]; 30 int f[MAXN]; 31 int sz,s[MAXN],nume; 32 int insert(char ch[]) 33 { 34 int k,len=strlen(ch),now=0; 35 Rep(p,len) 36 { 37 k=ch[p]-'a'; 38 if(t[now][k]==0) t[now][k]=++sz; 39 now=t[now][k]; 40 } 41 if(s[now]==0) s[now]=++nume; 42 return s[now]; 43 } 44 int get(int u) 45 { 46 return f[u]==u?u:f[u]=get(f[u]); 47 } 48 int degree[MAXN]; 49 char buf[2][10000]; 50 int main() 51 { 52 For(i,MAXN) 53 { 54 f[i]=i; 55 } 56 memset(degree,0,sizeof(degree)); 57 while(scanf("%s %s",buf[0],buf[1])!=2)//&&buf[0][0]!='0') 58 { 59 int idx1=insert(buf[0]), 60 idx2=insert(buf[1]); 61 degree[idx1]++; 62 degree[idx2]++; 63 // printf("idx1=%d idx2=%d\n",idx1,idx2); 64 int fa=get(idx1),fb=get(idx2); 65 if(fa!=fb) 66 { 67 f[fa]=fb; 68 } 69 } 70 int cnt1=0,cnt2=0; 71 for(int i=1;i<=nume;i++) 72 { 73 if(get(i)==i)cnt1++; 74 if(degree[i]%2==1)cnt2++; 75 if(cnt1>1)break; 76 if(cnt2>2)break; 77 } 78 if((cnt1==0||cnt1==1)&&(cnt2==0||cnt2==2)) 79 printf("Possible\n"); 80 else printf("Impossible\n"); 81 return 0; 82 83 return 0; 84 } View Code

自動機

hdu2222

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

字符串集合S，給出一個模式串T，問S中字符串在T中出現多少個，可重疊，S是multiset

trie樹的功能是判斷有沒有，出現在S中以及S中的成員關系，

相對的，自動機解決的是模式與模板之間的關系，

字符串集合的構造顯然和trie樹一樣，模板的匹配用的就和kmp一樣，

之后要注意的是在query時每匹配中一個字符串就要把val清空以防止重復統計

1 #include <stdio.h> 2 #include <string.h> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn=500000+10; 8 const int maxl=1000000+10; 9 queue<int>que; 10 struct trie{ 11 int a[maxn][26]; 12 int fail[maxn]; 13 int val[maxn]; 14 int sz,ans; 15 16 void init(){ 17 sz=0; 18 memset(a,0,sizeof(a)); 19 memset(val,0,sizeof(val)); 20 ans=0; 21 } 22 23 int idx(char c) { return c-'a'; } 24 25 void insert(char s[]){ 26 int i,n,now=0; 27 n=strlen(s); 28 for(i=0;i<n;i++){ 29 int id=idx(s[i]); 30 if(a[now][id]==0) a[now][id]=++sz; 31 now=a[now][id]; 32 } 33 val[now]++; 34 } 35 36 void acmatch(){ 37 fail[0]=0; 38 int i; 39 for(i=0;i<26;i++){ 40 int u=a[0][i]; 41 if(u){ 42 fail[u]=0;que.push(u); 43 } 44 } 45 while(!que.empty()){ 46 int r=que.front();que.pop(); 47 for(int c=0;c<26;c++){ 48 int u=a[r][c]; 49 if(!u) continue; 50 que.push(u); 51 int v=fail[r]; 52 while(v && !a[v][c]) v=fail[v]; 53 fail[u]=a[v][c]; 54 } 55 } 56 } 57 58 void query(char s[]){ 59 int i,n,now=0; 60 n=strlen(s); 61 for(i=0;i<n;i++){ 62 int id=idx(s[i]); 63 while(now && !a[now][id]){ 64 now=fail[now]; 65 } 66 now=a[now][id]; 67 int t=now; 68 while(t) 69 { 70 ans+=val[t]; 71 val[t]=0; 72 t=fail[t]; 73 } 74 } 75 } 76 }; 77 78 trie ac; 79 char str[maxl],word[100]; 80 81 int main() 82 { 83 int i,j,n,T; 84 scanf("%d",&T); 85 while(T--){ 86 ac.init(); 87 scanf("%d",&n); 88 for(i=0;i<n;i++){ 89 scanf("%s",word); 90 ac.insert(word); 91 } 92 ac.acmatch(); 93 scanf("%s",str); 94 ac.query(str); 95 printf("%d\n",ac.ans); 96 } 97 return 0; 98 } View Code

hdu2825

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

給定一個字符串集合S，給出一個模式串T的長度，問S中字符串在T中出現至少k次有多少種方案，S可以重疊

一開始想法是d[i][j][k]表示匹配到i長度，j狀態，出現k次，但是要注意的是可能重復出現S字符串，又k比較小

所以應該k換成s狀態壓縮表示已經出現的字符串集合。ac自動機+dp中，dp用到的是dp的單詞標記。

這題比較難代碼是抄的，有機會重現自己寫一遍。

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 const int MOD=20090717; 8 int n,m,k; 9 int dp[30][110][1<<10]; 10 int num[5000]; 11 12 struct Trie 13 { 14 int next[110][26],fail[110],end[110]; 15 int root,L; 16 int newnode() 17 { 18 for(int i = 0;i < 26;i++) 19 next[L][i] = -1; 20 end[L++] = 0; 21 return L-1; 22 } 23 void init() 24 { 25 L = 0; 26 root = newnode(); 27 } 28 void insert(char buf[],int id) 29 { 30 int len = strlen(buf); 31 int now = root; 32 for(int i = 0;i < len;i++) 33 { 34 if(next[now][buf[i]-'a']==-1) 35 next[now][buf[i]-'a'] = newnode(); 36 now = next[now][buf[i]-'a']; 37 } 38 end[now] |= (1<<id); 39 } 40 void acmatch() 41 { 42 queue<int>Q; 43 fail[root] = root; 44 for(int i = 0;i < 26;i++) 45 if(next[root][i] == -1) 46 next[root][i] = root; 47 else 48 { 49 fail[next[root][i]] = root; 50 Q.push(next[root][i]); 51 } 52 while(!Q.empty()) 53 { 54 int now = Q.front(); 55 Q.pop(); 56 end[now] |= end[fail[now]]; 57 for(int i = 0;i < 26;i++) 58 if(next[now][i] == -1) 59 next[now][i] = next[fail[now]][i]; 60 else 61 { 62 fail[next[now][i]] = next[fail[now]][i]; 63 Q.push(next[now][i]); 64 } 65 } 66 } 67 int solve() 68 { 69 //memset(dp,0,sizeof(dp)); 70 for(int i = 0;i <= n;i++) 71 for(int j = 0;j < L;j++) 72 for(int p = 0;p < (1<<m);p++) 73 dp[i][j][p]=0; 74 dp[0][0][0] = 1; 75 for(int i = 0;i < n;i++) 76 for(int j = 0;j < L;j++) 77 for(int p = 0;p< (1<<m);p++) 78 if(dp[i][j][p] > 0) 79 { 80 for(int x = 0;x < 26;x++) 81 { 82 int newi = i+1; 83 int newj = next[j][x]; 84 int newp = (p|end[newj]); 85 dp[newi][newj][newp] += dp[i][j][p]; 86 dp[newi][newj][newp]%=MOD; 87 } 88 } 89 int ans = 0; 90 for(int p = 0;p < (1<<m);p++) 91 { 92 if(num[p] < k)continue; 93 for(int i = 0;i < L;i++) 94 { 95 ans = (ans + dp[n][i][p])%MOD; 96 } 97 } 98 return ans; 99 } 100 }; 101 char buf[20]; 102 Trie ac; 103 int main() 104 { 105 for(int i=0;i<(1<<10);i++) 106 { 107 num[i] = 0; 108 for(int j = 0;j < 10;j++) 109 if(i & (1<<j)) 110 num[i]++; 111 } 112 while(scanf("%d%d%d",&n,&m,&k)==3) 113 { 114 if(n== 0 && m==0 &&k==0)break; 115 ac.init(); 116 for(int i = 0;i < m;i++) 117 { 118 scanf("%s",buf); 119 ac.insert(buf,i); 120 } 121 ac.acmatch(); 122 printf("%d\n",ac.solve()); 123 } 124 return 0; 125 } View Code

后綴數組

轉載于:https://www.cnblogs.com/diang/p/5704245.html

總結

以上是生活随笔為你收集整理的字符串入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： SQL SERVER 2000数据库置疑
下一篇： Breadth-first Search