Hướng dẫn giải của Xâu con

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 3
    ducquoc  đã bình luận lúc 9, Tháng 1, 2025, 16:53

    Bài này thật khó (ít nhất là với newbie như mình). Giải bằng các hàm so chuỗi thông thường (indexOf, substring, substr,...) dễ bị TLE (đặc biệt là test cuối - Test 6).

    May mà có các editorial tham khảo, các cách giải KMP hoặc Z-function, two-pointers.

    Tuy vậy chưa thấy có cách giải bằng rolling hash (Rabin-Karp), nên mình xin chia sẻ sample (impl Java):

    https://oj.vnoi.info/src/8127640 

    import java.io.*; import java.util.*;

// code mau cua ducquoc

@SuppressWarnings({"all"}) // https://oj.vnoi.info/problem/substr
class VoSubstr {
    public static void sol(PrintStream os) {
        QDS in = new QDS(); PrintWriter out = new PrintWriter(os);
        String A = in.next().trim(), B = in.next().trim();
        substr(A, B, out); out.close(); in.close();
    }

    static int PRIME = 31;
    static long MOD = 1_000_000_007, pow[], hashR[];

    static void substr(String A, String B, PrintWriter out) {
        int n = A.length(), m = B.length(); if (n < m) return;
        A = " " + A; B = " " + B; pow = new long[n + 1]; pow[0] = 1; hashR = new long[n + 1];
        for (int i = 1; i <= n; i++) pow[i] = (pow[i - 1] * PRIME) % MOD;
        for (int i = 1; i <= n; i++) hashR[i] = (hashR[i - 1] * PRIME + (A.charAt(i) - 'a' + 1)) % MOD;
        long hashB = 0; for (int i = 1; i <= m; i++) hashB = (hashB * PRIME + (B.charAt(i) - 'a' + 1)) % MOD;
        for (int i = 1; i <= n - m + 1; i++) {
            long subAHash = hashRolling(i, i + m - 1);
            if (hashB == subAHash) out.print(i + " ");
        }
        out.flush();
    }

    static long hashRolling(int l, int r) {
        return (hashR[r] - hashR[l - 1] * pow[r - l + 1] + MOD * MOD) % MOD;
    }

    final public static void main(String[] args) throws Exception { //System.setOut(new PrintStream("O.out"));
        System.setIn(new ByteArrayInputStream("aaaaa\naa".getBytes())); //FileInputStream("I.inp"));
        sol(System.out);
    }
}
/** quick data Scanner */
class QDS {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1024); StringTokenizer st;
    public String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(
            br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); }
    public int nextInt() { return Integer.parseInt(next()); }
    public void close() { if (br != null) { try { br.close(); } catch (IOException e) { e.printStackTrace(); } } }
}