Submission #32786655

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

class KMP {
  private :
    vector<int> f; // 比它小的最长前缀的长度
    char *s;
    int sz;
  public:
    KMP(char *s,int sz):s(s),sz(sz){
      f = vector<int>(sz,0);
      int fa = 0;
      rep(i,1,sz){
        while (fa && s[i] != s[fa]) fa = f[fa-1];
        if (s[i] == s[fa]) fa++;
        f[i] = fa;
      }
    }
    vector<int> getPrefixLen(){
      return f;
    }
    int posIn(char *t,int szt) {
      int fa = 0;
      rep(i,0,szt) {
        while (fa && t[i] != s[fa]) fa = f[fa-1];
        if (t[i] == s[fa]) fa++;
        if (fa == sz) return i-fa+1;
      }
      return -1;
    }
};

char s[1000010];

int ns;
int nt;
const int INF = 0x3f3f3f3f;

int main(){
  scanf("%s",s);
  int ns = strlen(s);
  s[ns] = '#';
  scanf("%s",s+ns+1);
  int nt = strlen(s+ns+1);
  int n = ns+1+nt;
  vector<int> dp(nt+1,INF);
  dp[0] = 0;
  KMP kmp(s, n);
  auto pl = kmp.getPrefixLen();
  // rep(i,0,nt){
  //   printf("%lld: %d\n",i,pl[i+ns+1]);
  // }

  rep(i,1,nt+1){
    dp[i] = dp[i-pl[i+ns]]+1;
    // printf("dp[%lld] = %d\n",i,dp[i]);
  }
  printf("%d\n", dp[nt] >= INF?-1:dp[nt]);

  return 0;
}

// k 个S前缀拼成 T
// KMP?

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:48:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%s",s);
      |   ~~~~~^~~~~~~~
./Main.cpp:51:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%s",s+ns+1);
      |   ~~~~~^~~~~~~~~~~~~

Judge Result