Submission #70607546

---

Source Code Expand

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#include <vector>
// MP
template<typename T>
class MP {
public:
	MP(const T& t) : t(t) {
		build();
	}
	std::vector<int> findAll(const T& s) {
		std::vector<int> res;
		int j = 0;
		for (int i = 0; i < s.size(); ++i) {
			while (j != -1 && t[j] != s[i]) j = a[j];
			j++;
			if (j == n) {
				res.push_back(i - j + 1);
				j = a[j];
			}
		}
		return res;
	}
	void dump() {
		for (auto e : a)std::cout << e << " ";
		std::cout << std::endl;
	}
private:
	int n;
	T t;
	std::vector<int> a;
	void build() {
		n = t.size();
		a = std::vector<int>(n + 1);
		a[0] = -1;
		int j = -1;
		for (int i = 0; i < n; ++i) {
			while (j != -1 && t[j] != t[i]) j = a[j];
			j++;
			a[i + 1] = j;
		}
	}
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t; cin >> t;
	while (t--) {
		string a, b;
		cin >> a >> b;
		a += a;
		MP mp(b);
		auto v = mp.findAll(a);
		if (v.empty()) {
			cout << -1 << endl;
		}
		else {
			cout << v[0] << endl;
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In instantiation of 'std::vector<int> MP<T>::findAll(const T&) [with T = std::__cxx11::basic_string<char>]':
./Main.cpp:70:22:   required from here
   70 |                 auto v = mp.findAll(a);
      |                          ~~~~~~~~~~^~~
./Main.cpp:31:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 for (int i = 0; i < s.size(); ++i) {
      |                                 ~~^~~~~~~~~~

Judge Result