Pagini recente » Cod sursa (job #1583668) | Monitorul de evaluare | Cod sursa (job #3304946) | Cod sursa (job #1579660) | Cod sursa (job #3238215)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
vector <int> sol;
vector <int> prefix(string s)
{
int n = (int)s.length();
vector <int> kmp(n);
for (int i = 1; i < n; i++)
{
int j = kmp[i-1];
while (j > 0 && s[i] != s[j])
j = kmp[j - 1];
if (s[i] == s[j])
j ++;
kmp[i] = j;
}
return kmp;
}
vector <int> matching(string s, string t)
{
string c = s + '!' + t;
vector <int> lg = prefix(c);
vector <int> poz;
for (int i = s.size() + 1; i < c.size(); i ++)
{
if (lg[i] >= s.size())
poz.push_back(i - s.size());
}
return poz;
}
int main()
{
string a, b;
cin >> a >> b;
sol = matching(a, b);
cout << sol.size() << '\n';
for (auto it : sol)
cout << it - a.size() << " ";
return 0;
}