Pagini recente » Cod sursa (job #2415455) | Cod sursa (job #2448104) | Cod sursa (job #2052441) | Cod sursa (job #3124076) | Cod sursa (job #2847656)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <stack>
#include <iomanip>
#include <list>
#include <chrono>
#include <random>
#include <numeric>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector<int> prefix_function(const string& s)
{
int n = s.length();
vector<int> pi(n);
for (int i = 1; i < n; i++)
{
int j = pi[i - 1];
while (j && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j])
j++;
pi[i] = j;
}
return pi;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> t >> s;
auto pi = prefix_function(t);
int j = 0;
vector<int> sol;
for (int i = 0; i < s.length(); i++)
{
while (j && s[i] != t[j])
j = pi[j - 1];
if (s[i] == t[j])
j++;
if (j == t.length())
{
sol.push_back(i - j + 1);
j = pi[j - 1];
}
}
cout << sol.size() << '\n';
for (int i=0;i<min(1000,(int)sol.size());i++)
{
cout << sol[i] << ' ';
}
cout << '\n';
return 0;
}