Pagini recente » Cod sursa (job #1571434) | Cod sursa (job #2293912) | Cod sursa (job #3040832) | Cod sursa (job #1292739) | Cod sursa (job #3182766)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[40005];
char s[40005];
char t[20005];
vector <int> v;
int main()
{
int n,i,j,l = 0,r = 0,cnt = 0,sz;
fin >> s;
n = strlen(s);
fin.get();
fin >> t;
sz = n + strlen(t);
strcat(s,t);
for(i = 1; i < sz; i++){
if(i > r){
int e = 0,x = i;
while(s[x] == s[e] && x < sz){
x++;
e++;
}
if(e){
l = i;
r = x - 1;
z[l] = r - l + 1;
}
}
else{
int k = i - l;
if(z[k] < r - i + 1) z[i] = z[k];
else{
int x = r,e = r - l,ok = 0;
while(s[x] == s[e] && x < sz){
x++;
e++;
ok = 1;
}
if(ok){
r = x - 1;
l = i;
z[i] = r - k + 1;
}
else z[k] = r - k + 1;
}
}
if(z[i] >= n && i >= n){
cnt++;
if(v.size() < 1000) v.push_back(i - n);
}
}
fout << cnt << "\n";
for(auto x : v) fout << x << " ";
return 0;
}