Pagini recente » Cod sursa (job #898386) | Cod sursa (job #1040235) | Cod sursa (job #2225299) | Cod sursa (job #2472277) | Cod sursa (job #2401673)
#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
{
pref[i] = 0;
j = 0;
}
}
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];
}
}
int sz = st.size();
printf("%d\n",sz);
while(!st.empty())
{
st2.push(st.top());
st.pop();
}
while(!st2.empty())
{
printf("%d ",(st2.top()));
st2.pop();
}
}