Pagini recente » Cod sursa (job #520890) | Cod sursa (job #1750685) | Cod sursa (job #1577769) | Cod sursa (job #1282087) | Cod sursa (job #1464046)
#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;
for(int i = 1; i < n; i++){
if(pattern[i] == pattern [lps[i-1]])
lps[i] = lps[i-1] + 1;
else {
if( lps[i-1] != 0)
lps[i] = lps[i-1];
else
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) {
occ++;
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 < pos.size(); i++) {
g << pos.at(i) << ' ';
}
}
int main()
{
readInput();
lpsCreation();
kmp();
return 0;
}