Editorial for Tách từ
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; z=1337377; type pointer=^node; node=record cnt:longint; next:array['a'..'z'] of pointer; end; var n,i,j:longint; a,s:ansistring; top:pointer; f:array[0..300030] of longint; function create:pointer; var c:char; p:pointer; begin new(p); p^.cnt:=0; for c:='a' to 'z' do p^.next[c]:=nil; exit(p); end; procedure put(p:pointer;pos:longint;s:ansistring); var t:pointer; begin if p^.next[s[pos]]=nil then p^.next[s[pos]]:=create; t:=p^.next[s[pos]]; if pos<length(s) then put(t,pos+1,s) else inc(t^.cnt); end; procedure check(p:pointer;pos,x:longint); var t:pointer; begin if p^.next[a[pos+x]]=nil then exit; t:=p^.next[a[pos+x]]; if t^.cnt>0 then begin f[pos+x]:=f[pos+x]+f[x]; if f[pos+x]>=z then f[pos+x]:=f[pos+x]-z; end; if (pos<100) and (pos+x<n) then check(t,pos+1,x); end; begin assign(input,fi); reset(input); readln(a); readln(n); top:=create; for i:=1 to n do begin readln(s); put(top,1,s); end; n:=length(a); f[0]:=1; for i:=0 to n-1 do check(top,1,i); writeln(f[n]); close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<cstring> const int N = 4000 + 2, L = 300000 + 2, WL = 100 + 2, MOD = 1337377; struct TrieNode { int next[26], nfinish; } trie[N * WL]; int nnode = 1, n, f[L]; char tmp[WL], s[L]; void insert(const char * s) { int u = 0; for(int i = strlen(s) - 1; i >= 0; --i) { int t = s[i] - 0x61; if(trie[u].next[t] == 0) trie[u].next[t] = nnode++; u = trie[u].next[t]; } trie[u].nfinish = 1; } void enter() { scanf("%s%d", s+1, &n); for(int i = 0; i < n; ++i) { scanf("%s", tmp); insert(tmp); } } void solve() { f[0] = 1; int l = strlen(s + 1); for(int i = 1; i <= l; ++i) { int u = 0; for(int j = i; j && trie[u].next[s[j] - 0x61]; --j) if(trie[u = trie[u].next[s[j] - 0x61]].nfinish) f[i] = (f[j-1] + f[i]) % MOD; } printf("%d\n", f[l]); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 300005; const int MOD = 1337377; using namespace std; char s[N], aa[111]; int f[N]; int n; struct node { int a[26]; int e; int& operator[] (int i) {return a[i];} node() {for(int i=0; i<26; i++) a[i] = 0; e = 0;} }; vector<node> a; void Add(char *s) { int pos = 0, i, c; for(i=0; c = s[i]; i++) { if (a[pos][c - 'a'] == 0) { a.push_back(node()); a[pos][c - 'a'] = a.size() - 1; } pos = a[pos][c - 'a']; } a[pos].e = 1; } int main() { gets(s); scanf("%d\n", &n); int i, j, pos, c; a.push_back(node()); for(i=1;i<=n; i++) { gets(aa); Add(aa); } f[0] = 1; for(i=0; s[i]; i++) { pos = 0; for(j=i; c = s[j]; j++) { if (a[pos][c - 'a'] == 0) break; pos = a[pos][c - 'a']; if (a[pos].e == 1) f[j+1] = (f[j+1] + f[i]) % MOD; } } printf("%d\n", f[strlen(s)]); return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung {$R-,Q-} const FINP=''; FOUT=''; MAXN=300111; oo=1337377; type trie=^node; node=record c:integer; d:array['a'..'z'] of trie; end; var s:ansistring; n:longint; root:trie; d:array[0..MAXN] of longint; procedure add(var t:trie); var ch:char; begin new(t); t^.c:=0; for ch:='a' to 'z' do t^.d[ch]:=nil; end; procedure inp; var a:string; i,j,m,l:longint; x:trie; begin assign(input,FINP); reset(input); readln(s); n:=length(s); readln(m); add(root); for i:=1 to m do begin readln(a); l:=length(a); x:=root; for j:=l downto 1 do begin if x^.d[a[j]]=nil then add(x^.d[a[j]]); x:=x^.d[a[j]]; end; inc(x^.c); end; close(input); end; procedure solve; var i,j:longint; x:trie; begin d[0]:=1; for i:=1 to n do begin x:=root; j:=i; while (j>0) and (x^.d[s[j]]<>nil) do begin x:=x^.d[s[j]]; dec(j); if x^.c=1 then inc(d[i],d[j]); end; d[i]:=d[i] mod oo; end; writeln(d[n]); end; begin inp; solve; end.
Code mẫu của ll931110
#include <cmath> #include <cstring> #include <iostream> #define MOD 1337377 using namespace std; struct trie { int val; int d[26]; } tx[400110]; int n,k,cnt = -1; char S[300010]; char a[105]; int F[300010]; int create() { cnt++; tx[cnt].val = 0; memset(tx[cnt].d,-1,sizeof(tx[cnt].d)); return cnt; } int main() { // freopen("strings.inp","r",stdin); // freopen("strings.out","w",stdout); scanf("%s", &S); n = strlen(S); int tmp = create(); scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%s", &a); int s = 0; for (int j = 0; j < strlen(a); j++) { int next = tx[s].d[a[j] - 'a']; if (next < 0) { next = create(); tx[s].d[a[j] - 'a'] = next; } s = next; } tx[s].val++; } memset(F,0,sizeof(F)); F[n] = 1; for (int i = n - 1; i >= 0; i--) { int s = 0,j = i; while (j < n) { s = tx[s].d[S[j] - 'a']; if (s < 0) break; j++; F[i] = (F[i] + tx[s].val * F[j]) % MOD; } } printf("%d\n", F[0]); }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> using namespace std; struct Trie { bool last; Trie * n[26]; }; Trie container[800000]; int ncon; int n, N; char a[300030], tmp[444]; Trie root; int f[300030]; const int mod = 1337377; void add( char * a) { Trie * p = &root; for(int i=0;a[i]!=0;++i) { int t = a[i] - 'a'; if(p->n[t]!=NULL) p = p->n[t]; else { p->n[t] = container + ++ncon; p = p->n[t]; } } p->last = true; } int main() { gets(a); n = strlen(a); scanf("%d", &N); gets(tmp); for(int i=0;i<N;++i) { gets(tmp); add( tmp); } f[n] = 1; for(int i=n-1;i>=0;--i) { Trie * p = &root; for(int j=i;j<n;++j) { int t = a[j] - 'a'; if(p->n[t]==NULL) break; p = p->n[t]; if(p->last) f[i] += f[j+1]; } f[i] %= mod; } cout << f[0] << endl; //system("pause"); return 0; }
Comments