Pagini recente » Cod sursa (job #1944961) | Cod sursa (job #155993) | Cod sursa (job #766135) | Cod sursa (job #206261) | Cod sursa (job #1390689)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX 2000002
#define cout fout
int k, i, n, pi[MAX];
char a[MAX], b[MAX];
vector<int> v;
void failure_func()
{
int k = 0;
for(i = 2 ; i <= n ; i++)
{
k = pi[i - 1];
while(k && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
{
k++;
}
pi[i] = k;
}
}
int main()
{
fin >> a+1 >> b+1;
n = strlen(a + 1);
failure_func();
k = 0;
for(i = 1 ; b[i] ; i++)
{
while(k && a[k + 1] != b[i])
{
k = pi[k];
}
if(a[k + 1] == b[i])
k++;
// cout << k << " ";
if(k == n)
{
v.push_back(i - n);
k = pi[k];
}
}
cout << v.size() << "\n";
for(i = 0 ; i < v.size() ; i++)
{
cout << v[i] << " ";
}
return 0;
}