Pagini recente » Cod sursa (job #615224) | Cod sursa (job #789858) | Cod sursa (job #2920824) | Cod sursa (job #240929) | Cod sursa (job #1464330)
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char text[2000001], pattern[2000001];
vector<int> pos;
int n, m;
int lps[2000001];
void readInput() {
f>>pattern>>text;
m = strlen(text);
n = strlen(pattern);
}
void lpsCreation() {
lps[0] = 0;
int i = 1, p = 0;
while(i < n){
if(pattern[i] == pattern[p]){
p++;
lps[i] = p;
i++;
}
else {
if(p != 0){
p--;
}
else {
lps[i] = 0;
i++;
}
}
}
}
void kmp() {
int i = 0, j = 0, occ = 0;
pos = vector<int>();
while(i < m) {
if(text[i] == pattern[j]) {
i++; j++;
}
if(j == n && i < m) {
occ++;
if(occ <= 1000)
pos.push_back(i - j);
j = lps[j-1];
}
else if (i < m && text[i] != pattern[j]) {
if(j != 0) {
j = lps[j-1];
}
else {
i++;
}
}
}
g<<occ<<'\n';
for(int i = 0; i < occ; i++) {
g << pos.at(i) << ' ';
}
}
int main()
{
readInput();
lpsCreation();
kmp();
return 0;
}