Pagini recente » Cod sursa (job #946160) | Cod sursa (job #2789760) | Cod sursa (job #3168463) | Cod sursa (job #269090) | Cod sursa (job #1390694)
#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 < 1000; i++)
{
cout << v[i] << " ";
}
return 0;
}