Editorial for Xâu con
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
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; int main() { int m,n,i=0,j=-1,pre[1000100]={-1}; char a[1000100],b[1000100]; scanf("%s%s",&a,&b); m=strlen(a); n=strlen(b); while (i<n) { while (j>=0 && b[i]!=b[j]) j=pre[j]; i++; j++; pre[i]=(j>=n || b[i]!=b[j]?j:pre[j]); } i=j=0; while (i<m) { while (j>=0 && a[i]!=b[j]) j=pre[j]; i++; j++; if (j>=n) j=pre[j], printf("%d ",i-n+1); } return 0; }
Code mẫu của happyboy99x
#include<cstdio> #include<cstring> const int N = 1e6; char s[N+1], t[N+1]; int next[N]; int main() { scanf("%s%s", t, s); next[0] = -1; for(int i = 1; s[i]; ++i) { int j = next[i-1]; while(j >= 0 && s[j+1] != s[i]) j = next[j]; if(s[j+1] == s[i]) ++j; next[i] = j; } for(int i = 0, j = -1; t[i]; ++i) { while(j >= 0 && t[i] != s[j+1]) j = next[j]; if(t[i] == s[j+1]) ++j; if(s[j+1] == 0) { printf("%d ", i - j + 1); j = next[j]; } } printf("\n"); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 2000006; using namespace std; string s, p; int Z[N]; void buildZ(const string &s, int Z[]) { int n = s.size(); Z[0] = 0; int l = 0, r = 0; for (int i = 1; i < n; ++i) { if (r < i) { l = r = i; while (r < n && s[r - l] == s[r]) ++r; Z[i] = r - l; --r; } else { int k = i - l; if (Z[k] < r - i + 1) { Z[i] = Z[k]; } else { l = i; while (s[r - l] == s[r]) ++r; Z[i] = r - l; --r; } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifdef _LAD_ freopen("SUBSTR.in", "r", stdin); #endif cin >> s >> p; s = p + '#' + s; buildZ(s, Z); for (int i = p.size() + 1; i < int(s.size()); ++i) if (Z[i] >= int(p.size())) cout << i - int(p.size()) << ' '; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> using namespace std; const int MN = 1000111; char s[MN], t[MN]; int next[MN]; int main() { scanf("%s\n", &t[1]); scanf("%s\n", &s[1]); int j; j = next[1] = 0; for(int i = 2; s[i]; ++i) { while (j > 0 && s[j+1] != s[i]) j = next[j]; if (s[j+1] == s[i]) ++j; next[i] = j; } j = 0; for(int i = 1; t[i]; ++i) { while (j > 0 && s[j+1] != t[i]) j = next[j]; if (s[j+1] == t[i]) ++j; if (s[j+1] == 0) { // Het xau s printf("%d ", i - j + 1); j = next[j]; } } puts(""); return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000000001 #define maxn 10011 #define oo 1111111111 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; void KMP(string text,string pattern){ int n = text.length(), m = pattern.length(), F[m+2],i,j; F[0] = F[1] = 0; for(int i = 2;i<=m;i++){ j = F[i-1]; while(true){ if(pattern[j] == pattern[i-1]) { F[i] = j+1; break;} else if(j==0) {F[i] = 0; break;} else j = F[j]; } } i = j = 0; while(j<n){ if(text[j] == pattern[i]){ i++; j++; if(i==m) printf("%d ",j-i+1); } else if(i>0) i = F[i]; else j++; } } int main(){ string a,b; cin>>a>>b; KMP(a,b); // getch(); }
Code mẫu của ll931110
//#pragma comment(linker, "/STACK:16777216") #include <algorithm> #include <bitset> #include <cmath> #include <ctime> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> #include <utility> using namespace std; string text,pattern; int f[1000010]; void build(string pattern) { f[0] = -1; for (int i = 1; i < pattern.size(); i++) { int j = f[i - 1]; for (; ;) { if (pattern[i] == pattern[j + 1]) { f[i] = j + 1; break; } if (j < 0) { f[i] = -1; break; } j = f[j]; } } } void KMP(string text) { int i = 0,j = -1; for (; ;) { if (i == text.size()) return; if (text[i] == pattern[j + 1]) { i++; j++; if (j >= pattern.size() - 1) { printf("%d ", i + 1 - pattern.size()); j = f[j]; } } else if (j >= 0) j = f[j]; else i++; } } int main() { // freopen("substr.in","r",stdin); // freopen("substr.ou","w",stdout); cin >> text >> pattern; build(pattern); KMP(text); }
Code mẫu của skyvn97
#include<cstdio> #include<cstring> #include<cstdlib> #define MAX 1010101 #define BASE 26 typedef long long ll; const ll mod[]={1e9+7,1e9+9,1e9+21,1e9+33}; char a[MAX]; char b[MAX]; int m,n; ll p[4][MAX]; ll sa[4][MAX]; ll sb[4][MAX]; void init(void) { scanf("%s",a); scanf("%s",b); int i,j; m=strlen(a); n=strlen(b); if (n>m) exit(0); for (i=0;i<2;i=i+1) { p[i][0]=1; for (j=1;j<=m;j=j+1) p[i][j]=(p[i][j-1]*BASE)%mod[i]; } for (i=0;i<2;i=i+1) { sa[i][0]=0; sb[i][0]=0; for (j=1;j<=m;j=j+1) sa[i][j]=(sa[i][j-1]+(a[j-1]-'a')*p[i][j-1])%mod[i]; for (j=1;j<=n;j=j+1) sb[i][j]=(sb[i][j-1]+(b[j-1]-'a')*p[i][j-1])%mod[i]; } } bool equal(int k,int a,int b) { int i; ll x,y; for (i=0;i<2;i=i+1) { x=(sa[i][a+k-1]-sa[i][a-1])%mod[i]; y=(sb[i][b+k-1]-sb[i][b-1])%mod[i]; if (a<b) x=x*p[i][b-a]; if (b<a) y=y*p[i][a-b]; if ((y-x)%mod[i]!=0) return (false); } return (true); } void process(void) { int i,j; for (i=1;i<=m-n+1;i=i+1) if (equal(n,i,1)) { printf("%d",i); break; } for (j=i+1;j<=m-n+1;j=j+1) if (equal(n,j,1)) printf(" %d",j); } int main(void) { init(); process(); return 0; }
Comments