Pagini recente » Cod sursa (job #210396) | Cod sursa (job #2736175) | Cod sursa (job #2331798) | Cod sursa (job #1471507) | Cod sursa (job #2833679)
#include<fstream>
#include<cstring>
#include<vector>
#define N 2000001
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char str[N], pat[N];
int resume[N], n, m;
vector<int> res;
void BuildMatch(char *pat){
resume[0] = 0;
int i = 0, j = 1;
while(j < m){
if(pat[i] == pat[j]){
resume[j] = i + 1;
i++; j++;
}
else{
if(i == 0)
resume[j] = 0, j++;
else
i = resume[i-1];
}
}
}
int cnt = 0;
void Search(char *str, char *pat){
BuildMatch(pat);
int i = 0, // str
j = 0; // pat
while(i < n){
//cout << i << " " << j << "\n";
if(str[i] == pat[j]){
i++, j++;
}
if(j == m){
cnt++;
if(res.size() < 1000)res.push_back(i-j); // de unde incepe sirul potrivit
j = resume[j-1];
}
else if(i<n && pat[j] != str[i]){
if(j){
j = resume[j-1];
}
else i++;
}
}
}
int main(){
cin >> pat >> str;
n = strlen(str);
m = strlen(pat);
//for(int i=0; i<m; i++) cout << resume[i] << " ";
Search(str, pat);
cout << cnt << "\n";
for(int i=0; i<res.size(); i++)
cout << res[i] << " ";
}