Pagini recente » Cod sursa (job #2701491) | Cod sursa (job #3275635) | Cod sursa (job #976807) | Cod sursa (job #2825133) | Cod sursa (job #2194286)
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;
char text[20000], pat[2000];
int f[20000];
vector<int> v;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
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 : v)
fout << i << ' ';
return 0;
}