Pagini recente » Cod sursa (job #2143028) | Cod sursa (job #937512) | Cod sursa (job #2987201) | Cod sursa (job #2411313) | Cod sursa (job #1051053)
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX_N 1000
int n, m;
char s1[MAX_N], s2[MAX_N];
void read(){
char f1[MAX_N], f2[MAX_N];
fin.get(f1,MAX_N);
fin.get();
fin.get(f2,MAX_N);
int n1 = strlen(f1);
int n2 = strlen(f2);
s1[0] = s2[0] = 'x';
strcat(s1,f2);
strcat(s2,f1);
n = strlen(s1)-1;
m = strlen(s2)-1;
}
int ol[MAX_N];
vector<int>list;
void overLap(){
for(int k=1; k<=m; k++){
char c = s2[k+1];
int v = ol[k];
while(s2[v+1] !=c && v!=0){
v = ol[v];
}
if(s2[v+1] == c)
ol[k+1] = v+1;
else
ol[k+1] = 0;
}
}
void solve(){
int i=1, j=1, k=1;
while(n-k >= m){
while(j <=m && s1[i] == s2[j]){
i++, j++;
}
if(j > m) list.push_back(k-1);
if(ol[j-1] > 0){
k = i - ol[j-1];
}else{
if(i==k) i++;
k = i;
}
if(j > 1) j= ol[j-1]+1;
}
if(k!=i){
bool ok = true;
for(int l=1; l<=m; l++){
if(s2[l]!=s1[k-1+l]) ok = false;
}
if(ok) list.push_back(k-1);
}
}
int main(){
read();
overLap();
solve();
fout << list.size() << endl;
for(size_t i = 0; i<list.size(); i++){
fout << list[i] << " ";
}
return 0;
}