I've written a story about anthropomorphic animals in a noirish setting solving murders. I came up with the concept and wrote the first draft about a year ago and am planning on releasing it soon. However, I recently saw a trailer for the movie Zootopia and realised that the basic premise is quite similar, even down to some of the characters. From the looks of things though, my story is far darker and more violent, and the humor style and themes are very different. I'm just worried that if released in such close proximity it might end up being accused of plagiarism.
There are only a few basic storylines. Some say there are only seven basic plots in all fiction. What differentiates different works is the telling. If the telling of your work reminds people too strongly of the telling of another work it will seem derivative. But if the basic story structure does not resemble one of the story archetypes written into the human psyche, it will just seem boring.
It is very common for writers to come up with similar ideas—sometimes extraordinarily similar. In some cases, it comes about from two writers being influenced by the same previous works. I remember, when X-Files was popular, quite a few people independently came up with TV series ideas that were basically "X-Files for kids". Other times, the connections are less obvious, but the idea just seems to be "in the air" somehow. Perhaps the sight of a generation staring at screens has spawned the current interest in zombie stories.
In any case, there's a fine line between one writer being influence by another (which is OK) and a writer plagiarizing another (which is not).
Although plagiarism of ideas (versus exact words) is explicitly not covered by copyright laws, that doesn't mean people can copy ideas with impunity. This kind of sleazy idea theft has been the basis of some very expensive lawsuits. In your case, since you didn't copy the other work, and your work is not similar to it in tone, I don't think you have much to worry about. A film noir animal murder mystery is unusual but not unique. The same idea underlies the comic book Blacksad, and Who Killed Roger Rabbit? It's a niche genre.
George Lucas wrote a Flash Gordon movie, but couldn’t get the rights to produce it. So he changed all the names of the characters and changed the title to Star Wars.
So short answer: no, it doesn’t matter. Plagiarism is when you literally copy/paste pieces of someone else’s work into your own, not when your story belongs in the same section of the bookstore as someone else’s work.
If you make your story unique and different, it doesn't matter. Maybe you know "The Hunger Games" by Susan Collins. The storyline is practly the same than "Battle Royale" by Coshun Takami. The idea of a group of people stucked in a place killing each other, is the same, but Susan Collins put her own style turning it into a TV show. Same story line, totally different results. My advice? Make the story yours.
I worry about doing this a lot when I'm writing my story, which right now is about cats and dogs who fight and go on adventures based on that. It reminds me a lot of Warrior cats series. And what's more, I decided to write this fantasy story right after READING the Warrior Cats series'. I have read the comments above, and also think that as long as your story is your idea, it is fine. Just don't write something based off of another author's plot.
If you came up with your story BEFORE you found another idea that is similar(like your problem), you know yourself that you aren't plagiarizing, since you didn't know. It was YOUR idea. The publishers can still accuse you, of course, but no matter what they think, you aren't copying. If you came up with your story AFTER you found a different idea that is similar, you want to be careful not to base your plot in the same way. But if you are inspired and just use a couple of the same main ideas, that's perfectly fine.