Pagini recente » Cod sursa (job #1513615) | Cod sursa (job #2186108) | Cod sursa (job #1858467) | Cod sursa (job #2158368) | Cod sursa (job #2149236)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N_MAX = 2e6;
string a, b;
int pi[N_MAX + 2];
int nrAns;
vector<int> posAns;
int main()
{
in >> a >> b;
b = a + '*' + b;
int x = 0;
for(int i = 2; i <= b.length(); i++)
{
while(x != 0 && b[x + 1] != b[i])
x = pi[x];
x += (b[x + 1] == b[i]);
pi[i] = x;
if(pi[i] == a.length() - 1)
{
nrAns++;
if(nrAns <= 1000)
posAns.push_back(i - 2 * a.length());
}
}
out << nrAns << '\n';
vector<int>::iterator it;
for(it = posAns.begin(); it != posAns.end(); it++)
out << *it << ' ';
return 0;
}