101498B - Longest Prefix
21 Nov 2020 — Tags: greedy — URL- Greedily match the characters of the second string to the first string.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
string a, b;
vi bcnt(26);
cin >> a >> b;
for (auto ch : b)
bcnt[ch - 'a']++;
int i = 0, n = (int)(a).size();
while (i < n and bcnt[a[i] - 'a'] > 0)
{
bcnt[a[i] - 'a']--;
++i;
}
cout << i << endl;
}
return 0;
}