Pagini recente » Cod sursa (job #2625063) | Cod sursa (job #2281730) | Cod sursa (job #371438) | Cod sursa (job #1269943) | Cod sursa (job #2725328)
#include <fstream>
#include <sstream>
#include <vector>
#define maxRange 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m,n, pi[maxRange];
string a,b;
vector <int> v;
void prefix()
{
int k = 0;
pi[0] = 0;
for(int i = 1; i < m; i++)
{
while(k && a[k] != a[i]) k = pi[k];
if(a[k] == a[i]) k++;
pi[i] = k;
}
}
int main()
{
f >> a;
f >> b;
m = a.length();
n = b.length();
prefix();
int q = 0;
for(int i = 0; i < n; i++)
{
while(q && a[q] != b[i]) q = pi[q];
if(a[q] == b[i]) q++;
if (q == m) q = pi[m-1],v.push_back(i-m+1);
}
g << v.size() << '\n';
for(int i = 0; i < v.size() && i < 1000; i++)
{
g << v[i] << ' ';
}
return 0;
}