Pagini recente » Cod sursa (job #928251) | Cod sursa (job #2406605) | Cod sursa (job #658597) | Cod sursa (job #181965) | Cod sursa (job #1578344)
#include <fstream>
#include <string>
#include <vector>
#define N 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
vector< int > sol;
int z[N], n, m, i, j, k, L, R, cnt;
int main()
{
f >> b ;
f >> a;
n = a.size();
m = b.size();
for(i = 1; i < m; i++)
{
if(i > R)
{
for(j = 0, k = i; b[j] == b[k] && k < m; k++, j++);
z[i] = j;
L = i;
R = i+j-1;
continue;
}
j = i-L;
if(i+z[j]-1 < R)
{
z[i] = z[j];
continue;
}
for(k = R+1, j = R-L+1; b[j] == b[k] && k < m; k++, j++);
z[i] = j;
L = i;
R = i+z[i]-1;
}
R = -1;L=0;
for(i = 0; i < n; i++)
{
if(i > R)
{
for(j = 0, k = i; b[j] == a[k] && k < n; k++, j++);
L = i;
R = k-1;
if(R-L+1 == m)
{
cnt++;
if(cnt <= 1000)
sol.push_back(L);
}
continue;
}
j = i-L;
if(i+z[j]-1 < R)
continue;
for(k = R+1, j = R-L+1; b[j] == a[k] && k < n; k++, j++);
L = i;
R = k-1;
if(R-L+1 == m)
{
cnt++;
if(cnt <= 1000)
sol.push_back(L);
}
}
g << cnt << '\n';
for(auto it : sol)
g << it << ' ';
return 0;
}