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.

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

Please read the guidelines before commenting.


  • 1
    ducquoc  commented on Jan. 9, 2025, 4:53 p.m.

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