Please help me...

Revision en2, by saiful_islam_bk, 2026-06-02 23:35:50

Can anyone tell me why my solution is getting WA?

Problem Link: https://www.spoj.com/problems/LCS2/

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define nl "\n"
#define pb push_back
#define saiful_islam_bk ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//String Automation:
struct state{
  int len, link, oc=0, in=0;
  unordered_map<char, int>next;
};
struct automata{
  public:
  vector<state>node;
  int last=0, sz=0, cur=0;
  automata(){
    node.clear(); node.resize(1);
    node[0].len=0; node[0].link=-1;
    sz=1; last=0;
  }
  void add(string s){
    last=0;
    for(int i=0; i<s.size(); i++){
      cur=sz++; node.pb(state());
      node[cur].len=node[last].len+1;
      node[cur].next.clear();
      node[cur].oc=1;
      while(last!=-1 && !node[last].next.count(s[i])){
        node[last].next[s[i]]=cur; last=node[last].link;
      }
      if(last==-1){
        node[cur].link=0;
      }else{
        int q=node[last].next[s[i]];
        if(node[last].len+1==node[q].len){
          node[cur].link=q;
        }else{
          int clone=sz++; node.pb(state());
          node[clone]=node[q];
          node[clone].len=node[last].len+1;
          node[clone].oc=0;
          while(last!=-1 && node[last].next[s[i]]==q){
            node[last].next[s[i]]=clone;
            last=node[last].link;
          }
          node[q].link=clone;
          node[cur].link=clone;
        }
      }
      last=cur;
    }
  }
  void order(int p){
    vector<int>ord(sz), cnt(p+5, 0);
    for(int i=0; i<sz; i++) cnt[node[i].len]++;
    for(int i=1; i<=p; i++) cnt[i]+=cnt[i-1];
    for(int i=sz-1; i>=0; i--) ord[--cnt[node[i].len]]=i;
    for(int i=sz-1; i>0; i--) node[node[ord[i]].link].oc+=node[ord[i]].oc;
  }
};

void solve(){
  string a, b, c; cin>>a>>b>>c; automata suf1, suf2;
  suf1.add(a); suf1.order(a.size());
  suf2.add(b); suf2.order(b.size());
  int ans=0, l=0, r=0, m1=0, m2=0;
  for(int i=0; i<c.size(); i++){
    if(suf1.node[m1].next.count(c[i])) l++, m1=suf1.node[m1].next[c[i]];
    else{
      while(m1 && !suf1.node[m1].next.count(c[i])){
        m1=suf1.node[m1].link;
      }
      if(suf1.node[m1].next.count(c[i])) l=suf1.node[m1].len+1, m1=suf1.node[m1].next[c[i]];
      else m1=0, l=0;
    }
    if(suf2.node[m2].next.count(c[i])) r++, m2=suf2.node[m2].next[c[i]];
    else{
      while(m2 && !suf2.node[m2].next.count(c[i])){
        m2=suf2.node[m2].link;
      }
      if(suf2.node[m2].next.count(c[i])) r=suf2.node[m2].len+1, m2=suf2.node[m2].next[c[i]];
      else m2=0, r=0;
    }
    ans=max(ans, min(l, r));
  }
  ans=max(ans, min(l, r));
  cout<<ans<<nl;
}
int32_t main(){
 saiful_islam_bk
 int test=1;
  // cin>>test;
 for(int ii=1; ii<=test; ii++){
    //cout<<"Case "<<ii<<": ";
    solve();
 }
}
Tags suffix automata, string, substring

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English saiful_islam_bk 2026-06-02 23:35:50 399
en1 English saiful_islam_bk 2026-06-02 23:34:51 3321 Initial revision (published)