Pagini recente » Cod sursa (job #1177921) | Cod sursa (job #138645) | Cod sursa (job #2025824) | Cod sursa (job #436639) | Cod sursa (job #2803491)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("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;
fin >> s >> t;
vector<int> ans = FindMatches(s, t);
fout << cnt <<'\n';
for(auto i : ans)
fout << i << ' ';
}