Pagini recente » Cod sursa (job #831734) | Cod sursa (job #1218706) | Cod sursa (job #1389571) | Cod sursa (job #1140663) | Cod sursa (job #1231840)
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
#define LMAX 2000009
#pragma warning(push)
#pragma warning(disable:4996)
string T, P;
int urm[LMAX];
int n, m;
int counter = 0;
vector<int> solutii;
void Urmatorul(string P)
{
int k = -1;
urm[0] = 0;
for (int i = 1; i < P.size(); ++i)
{
while (k > 0 && P[k + 1] != P[i])
k = urm[k];
if (P[k + 1] == P[i])
k++;
urm[i] = k;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> P;
cin >> T;
Urmatorul(P);
n = T.size();
m = P.size();
int k = -1;
for (int i = 0; i < n; ++i)
{
while (k > 0 && P[k + 1] != T[i])
k = urm[k];
if (P[k + 1] == T[i]) // s-au potrivit
k++;
if (k == m - 1)
{
solutii.push_back(i - m + 1);
k = urm[k];
counter++;
}
}
printf("%d\n", counter);
for (int i = 0; i < solutii.size(); ++i)
{
printf("%d ", solutii[i]);
}
return 0;
}
#pragma warning(pop)