Pagini recente » Cod sursa (job #928856) | Cod sursa (job #853498) | Cod sursa (job #3292283) | Cod sursa (job #3220440) | Cod sursa (job #2476518)
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int z[4000010];
void calcz(string s)
{
int len=s.length();
// cout<<len<<'\n';
int i,left,right;
left=right=0;
for(i=1;i<len;i++)
{
// cout<<i<<'\n';
if(i>right)
{
left=right=i;
while(s[right]==s[right-left] && right<len)
right++;
z[i]=right-left;
right--;
}
else
{
if( z[i-left]< right-i)
z[i]=z[i-left];
else
{
left=i;
while(s[right]==s[right-left] && right<len)
right++;
z[i]=right-left;
right--;
}
}
}
}
int main()
{
ifstream t1("strmatch.in");
ofstream t2("strmatch.out");
t1>>s1>>s2;
string aux=s1+"~"+s2;
int len=s1.length();
calcz(aux);
int sol=0,i;
queue<int> q;
for(i=len+1;i<aux.length();i++)
if(z[i]==len)
{
sol++;
q.push(i-len-1);
}
t2<<sol<<'\n';
while(!q.empty())
{
t2<<q.front()<<' ';
q.pop();
}
t1.close();
t2.close();
return 0;
}