Pagini recente » Cod sursa (job #2455367) | Cod sursa (job #3194750) | Cod sursa (job #1288655) | Cod sursa (job #1531864) | Cod sursa (job #2801841)
//https://infoarena.ro/problema/strmatch
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector <int> KMP(string s)
{
s = "$" + s;
vector <int> pi(s.size());
int k = 0;
for(int i = 2; i < (int)s.size(); i++)
{
while(k != 0 && s[i] != s[k+1])
k = pi[k];
if(s[i] == s[k+1])
k++;
pi[i] = k;
}
return pi;
}
int cnt = 0;
vector <int> FindMatches(string s, string t)
{
string to_kmp = s + "$" + t;
vector <int> kmp= KMP(to_kmp);
vector <int> ans;
for(int i = (int)s.size()+1; i < (int)kmp.size(); i++)
{
if(kmp[i] == (int)s.size())
ans.push_back(i - 2*s.size()-1), cnt++;
}
return ans;
}
int main()
{
string s, t;
in >> s >> t;
vector<int> ans = FindMatches(s, t);
out << cnt <<'\n';
for(int i = 0; i < min(cnt, 1000); i++)
{
out << ans[i]<<" ";
}
}