Pagini recente » Cod sursa (job #3253070) | Cod sursa (job #1907380) | Cod sursa (job #655009) | Cod sursa (job #2601919) | Cod sursa (job #1069941)
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MAX_N 10000000000001
int n, m;
char* s1, *s2;
void read(){
char f1[MAX_N], f2[MAX_N];
fin.get(f1,MAX_N);
fin.get();
fin.get(f2,MAX_N);
s1 = new char();
s2 = new char();
strcat(s1,"x");
strcat(s2,"x");
strcat(s1,f2);
strcat(s2,f1);
m = strlen(s2)-1;
n = strlen(s1)-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-1){
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;
}
}
int main(){
read();
overLap();
solve();
fout << list.size() << endl;
for(size_t i = 0; i<list.size(); i++){
fout << list[i] << " ";
}
return 0;
}