Pagini recente » Cod sursa (job #1853869) | Cod sursa (job #1520786) | Cod sursa (job #483714) | Cod sursa (job #1285223) | Cod sursa (job #2429468)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;
int p[2000000], N;
vector<int> poz;
void f_prefix(int &n)
{
int k = 0;
p[0] = 0;
for(int i = 1; i < n; i++)
{
while(k && A[i] != A[k])
k = p[k-1];
if(A[i] == A[k])
k++;
p[i] = k;
}
}
void f_potrivire(int &n, int &m)
{
int k = 0;
for(int i = 0; i < m; i++)
{
while(k && B[i] != A[k])
k = p[k-1];
if(B[i] == A[k])
k++;
if(k == n && ++N <= 1000)
poz.push_back(i-n+1);
}
}
int main()
{
in >> A >> B;
int n = A.size();
int m = B.size();
f_prefix(n);
f_potrivire(n,m);
out << N << '\n';
for(int i = 0; i < poz.size(); i++)
out << poz[i] << ' ';
return 0;
}