Pagini recente » Cod sursa (job #1614274) | Clasament pc_11a | Cod sursa (job #2567626) | Cod sursa (job #2750274) | Cod sursa (job #2194288)
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;
char text[2000010], pat[2000010];
int f[2000010];
vector<int> v;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int mini(int a,int b)
{
return a<b ? a:b;
}
void read()
{
fin.getline(pat, 2000001);
fin.getline(text, 2000001);
}
void fai(char* pat)
{
int j = 0;
int len = strlen(pat);
f[0] = 0;
for (int i = 1; i < len; i++)
{
while (pat[i] != pat[j] && j > 0) j = f[j-1];
if (pat[i] == pat[j]) j++;
f[i] = j;
}
}
void KMP()
{
int j = 0;
int n = strlen(text);
int m = strlen(pat);
for (int i = 0; i < n; i++)
{
while (text[i] != pat[j] && j > 0)
j = f[j];
if (text[i] == pat[j])
{
if (j == m - 1)
{
v.push_back(i - m + 1);
j = f[j];
}
else
j++;
}
}
}
int main()
{
read();
fai(pat);
KMP();
fout << v.size()<<'\n';
for (int i = 0;i<mini(1000,v.size());i++)
fout<<v[i]<<' ';
return 0;
}