Pagini recente » Istoria paginii utilizator/diana99ro | Cod sursa (job #1796056) | Istoria paginii utilizator/denekawa | Istoria paginii utilizator/stewie368 | Cod sursa (job #1691856)
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, s, space(" ");
int v[NMAX];
void build_prefix(string);
void KMP();
int main()
{
fin >> pattern;
fin >> s;
//pattern =space+pattern;
//s = space + s;
build_prefix(pattern);
KMP();/*
fout << '\n';
for (int i = 0; i < pattern.size(); i++)
fout << v[i];
fout << '\n' << pattern;
*/
return 0;
}
void build_prefix(string p)
{
v[0] = -1;
v[1] = 0;
int k=0;
for (int i = 2; i < p.size(); i++)
{
k = v[i - 1];
while (k!=-1&&p[i-1] != p[k])
k = v[k];
v[i] = k + 1;
}
//return v;
}
void KMP()
{
int k=0;
bool ok;
queue<int> q;
for (int i = 0; i < s.size(); i++)
{
ok = 0;
while (k!=-1&&pattern[k + 1] != s[i])
k = v[k];
k++;
if (k == pattern.size()-1)
{
k = v[k];
//if (q.size() < 1000)
q.push(i-pattern.size()+1);
}
}
_end:
int contor = 0;
fout << q.size()<<'\n';
while (!q.empty() && contor <= 1000)
{
contor++;
fout << q.front() << ' ';
q.pop();
}
}