Pagini recente » Cod sursa (job #352163) | Cod sursa (job #3182867)
#include <bits/stdc++.h>
#define NMAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[NMAX * 2 + 5];
char s[NMAX * 2 + 5];
char t[NMAX + 5];
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) z[i] = min(r - i, z[i - l]);
while(i + z[i] < sz && s[z[i]] == s[i + z[i]]) z[i]++;
if(i + z[i] > r){
l = i;
r = i + z[i];
}
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;
}