Pagini recente » Cod sursa (job #3205717) | Cod sursa (job #3229370) | Cod sursa (job #71962) | Cod sursa (job #2732438) | Cod sursa (job #2780322)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int lim = 2e6 + 5;
string pat;
string txt;
vector<int>sol;
int kmp[lim];
void preprocess()
{
int curr = 0;
for (int i = 1; i < pat.size(); i++)
{
while (curr && pat[curr] != pat[i])
curr = kmp[curr-1];
if (pat[i] == pat[curr])
curr++;
kmp[i] = curr;
}
}
void match()
{
int j = 0;
for (int i = 0; i < txt.size(); i++)
{
while (j && pat[j] != txt[i])
j = kmp[j - 1];
if (pat[j] == txt[i])
j++;
if (j == pat.size())
{
sol.push_back(i-j+1);
j = kmp[j-1];
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> pat;
cin >> txt;
preprocess();
match();
cout << sol.size() << '\n';
for (int i = 1; i <= min((int)sol.size(), 1000); i++)
cout << sol[i - 1] << " ";
}