Pagini recente » Cod sursa (job #2003732) | Cod sursa (job #1520262) | Statistici Nicolescu Razvan (rzvrzv) | Profil M@2Te4i | Cod sursa (job #2401746)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int NMAX = 2e6+5;
string s[2];
int pref[NMAX];
stack<int> st,st2;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int M,N,i,j;
cin>>s[0]>>s[1];
//match 0 in 1
N = s[0].size();
M = s[1].size();
for(i = 1 , j = 0 ; i < N ; ++i)
{
if(s[0][i] == s[0][j])
pref[i] = ++j;
else
{
if(j > 0)
{
j = pref[j-1];
i--;
}
}
}
for(i = j = 0 ; i < M ; ++i)
{
if(s[1][i] == s[0][j])
{
if(j == N - 1)
{
st.push(i - j);
j = pref[j];
}
else
j++;
}
else
{
if(j > 0)
{
j = pref[j-1];
i--;
}
}
}
int sz = st.size();
printf("%d\n",sz);
while(!st.empty())
{
st2.push(st.top());
st.pop();
}
i = 1;
while(!st2.empty() && i <= 1000)
{
printf("%d ",(st2.top()));
st2.pop();
i++;
}
return 0;
}