Pagini recente » Cod sursa (job #1749706) | Cod sursa (job #2470176) | Cod sursa (job #1296439) | Cod sursa (job #1726981) | Cod sursa (job #3242079)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void createLPS(string s, vector<int> &lps){
int i = 1, j = 0;
int n = s.length();
while(i < n){
if(s[i] == s[j]){
j++;
lps[i] = j;
i++;
}
else{
if(j>0){
j = lps[j-1];
}
else{
lps[i] = 0;
i++;
}
}
}
}
int main(){
string p, s;
int spotted = 0;
getline(in, p);
getline(in, s);
vector<int> pos(1000);
vector<int> lps(p.length()); // pattern array
createLPS(p, lps);
//Knuth Morris Pratt
int i = 0, j = 0;
while(i < s.length()){
if(s[i] == p[j]){
i++;
j++;
}
if(j == p.length()){
pos[spotted++] = i - j;
if(spotted == 1000)
break;
j = lps[j-1];
}
if(s[i] != p[j]){
if(j == 0){
i++;
}
else{
j = lps[j-1];
}
}
}
out << spotted << endl;
for(int i = 0; i<spotted; i++)
out << pos[i] << " ";
}